Proving the equivalence of two definitions of NFA acceptance

Question

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.

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