Recall that an NFA $N = (Q,\Sigma,\delta,S,F)$ accepts $w=w_1w_2\ldots w_n$, where $w_i \in \Sigma$, if one of the following holds:

(a) $\hat\delta(S,w) \cap F \neq \emptyset$, where $\hat\delta\colon P(Q) \times \Sigma^* \to P(Q)$ is given by $$ \hat\delta(Q',w) = \begin{cases} Q' & w = \epsilon \\ \bigcup_{q \in \hat\delta(q',w_1\ldots w_{n-1})} \delta(q,w_n) & |w| = n > 0 \end{cases} $$

(b) $\exists r_0,\ldots,r_n$, where $r_i \in Q$, such that:

  • $r_0 = q_0$

  • $r_n \in F$

  • $r_{i+1} \in \delta(r_i,w_{i+1})$

Show that (a) $\leftrightarrow$ (b)

I think I have proven from (b) to (a) but I'm not sure, and I seem to have no idea where to start the other way around. This is part of the first exercise in the computational models course I'm taking and I would really appreciate the help.


1 Answer 1


Just a hint:

  • First, generalize the problem: show that, for any $q\in Q$ and any word $w$, $q \in\hat\delta(S,w)$ if and only if $\exists r_0,...,r_{|w|}\in Q$ such that $r_0\in S$, $r_{|w|}=q$, and $r_{i+1}\in\delta(r_i, w_{i+1})$.

  • Second, show this statement by induction on the length $|w|$ of $w$. This is trivial for the base case, and should be easy for the inductive case, just apply the induction hypothesis and the definition of $\hat\delta$.

  • Finally, show that your equivalence follows from the general statement: apply it for any $q\in F$.


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.