# Non-deterministic Finite Automata | Sipser Example 1.16

I am working through the Sipser Book (2nd edition) and came across this example, which I do not understand. In the book it states that this NFA accepts the empty string, $$\epsilon$$.

Could someone run me through why this is the case?

My understanding is that $$\epsilon$$ will move to $$q_3$$ which is not an accept state.

You are confusing $$\epsilon$$ with a letter. It's not a letter! It's just the empty string.

Let us consider a slightly more general model, "word-NFA". A word-NFA is like an NFA, but each transition is labeled with an arbitrary word. We say that the word-NFA accepts a word $$w$$ if there is a walk from an initial state to a final state such that if we concatenate the edge labels across the walk, we get $$w$$. In symbols, a word-NFA accepts $$w$$ if there is a sequence of transitions $$q_0 \stackrel{w_1}\to q_1 \stackrel{w_2}\to q_2 \stackrel{w_3}\to \cdots \stackrel{w_n}\to q_n$$ such that:

1. $$q_0$$ is an initial state. (The usual model only allows one initial state, but we can relax that requirement.)
2. $$q_n$$ is a final state (also called an accepting state).
3. Each transition $$q_{i-1} \stackrel{w_i}\to q_i$$ corresponds to a transition of the word-NFA.
4. $$w = w_1 \ldots w_n$$.

An NFA is a word-NFA in which all transitions are labeled by letters (i.e., words of length exactly 1), and an $$\epsilon$$-NFA is one in which all transitions are labeled by letters or $$\epsilon$$ (i.e., words of length at most 1). Usually we also require that there be a unique initial state.

A word-NFA accepts $$\epsilon$$ if there is a sequence of transitions $$q_0 \stackrel\epsilon\to q_1 \stackrel\epsilon\to \cdots \stackrel\epsilon\to q_n$$ such that $$q_0$$ is an initial state, $$q_n$$ is a final state, and all transitions are valid. In particular, if some state is both initial and final, then the word-NFA accepts $$\epsilon$$ (this correponds to $$n = 0$$).

• AHA, thank you this makes sense now. So intuitively when we get $\epsilon$ we have two "branches": $q1 \rightarrow q1$ and $q1 \rightarrow q3$. Since $q1 \rightarrow q1$ is an accept state, we accept $\epsilon$ – Convex Leopard May 12 '19 at 19:22
• Yes, that’s a nice description. – Yuval Filmus May 12 '19 at 19:29