Equivalence of NDA definitions

Question

I have no clue how to tackle the follwing...

Given the following definitions of NFA, show that if an NFA accepts a string according to definition 1, it also does so according to definition 2.

\begin{align*}&\textbf{Definition 1: }N=(Q,\Sigma,\delta,S,F)\text{ accepts }w\in\Sigma^{\ast}\text{ if }\hat\delta(S,w)\cap F\ne\emptyset \\ &\textbf{Definition 2: }N=(Q,\Sigma,\delta,S,F)\text{ accepts }w\in\Sigma^{\ast} \text{ if }\exists a=(a_1a_2\dots a_k)\in\left(\Sigma\cup\{\varepsilon\}\right)^k \\&\text{ and }r_0,r_1,\dots,r_k\in Q\text{ s.t }: \\ &\bullet w=d(a) \text{ where }d(a)\text{ is }a\text{ without }\varepsilon \text{ symbols} \\ &\bullet r_0\in S \\ &\bullet r_k\in F \\ &\bullet r_{i+1}\in\delta(r_i,a_{i+1})\text{ for }0\le i<k\end{align*}

I started with def 1 and tried to use induction on string length to prove the claim, but to no avail.

Any help will be appreciated. Thanks!

Answer 1

Suppose that $N$ accepts $w$ according to Definition $1$. Let $w=(a_1a_2\ldots a_k)\in\Sigma^*$; then there are $r_0,r_1,\ldots,r_k\in Q$ such that

• $r_0\in S$,
• $r_k\in F$, and
• $r_{i+1}\in\delta(r_i,a_{i+1})$ for $0\le i<k$.

This is the special case of Definition $2$ in which $a=w$.

The point here is that Definition $2$ allows $\epsilon$-moves, transitions with no actual input, and Definition $1$ does not. If $w\in\Sigma^*$ can ‘drive’ $N$ to an acceptor state without using any $\epsilon$-transition, then it can certainly do so if $N$ also allows some $\epsilon$-transitions: it just doesn’t need to use any of them.