# Proving the equivalence of two definitions of NFA acceptance

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.

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