0
$\begingroup$

The following statement seems trivial, but how can it be formally proven/argued?

$$\bigcup_{s \in \delta_{N}^{*}\left(q_{0}, w\right)} \delta_{N}^{*}(s, a) \;\equiv\; \delta_{N}^{*}\left(q_{0}, w a\right)$$

In words: taking the union of the states when reading a symbol ‘a’ from all the possible states in a NFA having read the string ‘w’ from the start state, is the same as taking all the possible states we can get after reading the string ‘wa’ from the start state of the NFA.

$\endgroup$
2
  • 1
    $\begingroup$ Can you replace the (huge) image with a LaTeX formula? $\endgroup$
    – Steven
    Aug 27, 2022 at 15:38
  • $\begingroup$ @Steven, done. Thanks for the feedback. $\endgroup$
    – Ronald
    Aug 27, 2022 at 16:04

1 Answer 1

1
$\begingroup$

You can show that all states in the set on the left hand side are included in the set on the right hand side, and vice-versa.

$s \in \delta_N^*(q, w)$ if and only if there is some path $\pi(q,s,w)$ from state $q$ to state $s$ in $N$ such that the concatenation of the edge labels (which might be $\varepsilon$) is equal to $w$.

If $q$ is in the left hand union then there is some state $s \in \delta^*_N(q_0, w)$ such that $q \in \delta^*_N(s,a)$. Then $\pi(q_0,s,w) \circ \pi(s,q,a)$ is a path from $q_0$ to $q$ that matches $wa$, showing that $q \in \delta^*_N(q_0, wa)$.

On the other hand, if $q \in \delta^*_N(q_0, wa)$, let $s$ be the last occurrence of a state in $\pi(q_0, q, wa)$ such that the edge leaving $s$ is labelled $a$. The subpath of $\pi(q_0, q, wa)$ from $q_0$ to $s$ is such that the concatenation of its edge labels equals $w$. This shows that $s \in \delta^*_N(q_0, w)$. Moreover the subpath of $\pi(q_0, q, wa)$ from $s$ to $q$ is such that the concatenation of its edge labels equals $a$. This shows that $q \in \delta^*_N(s, a)$. Therefore $q$ belongs to the union in the left hand side.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.