# Extended transition function in NFA

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.

• Can you replace the (huge) image with a LaTeX formula? Aug 27, 2022 at 15:38
• @Steven, done. Thanks for the feedback. Aug 27, 2022 at 16:04

$$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.