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:

• $q_0$ is an initial state. (The usual model only allows one initial state, but we can relax that requirement.)

• $q_n$ is a final state (also called an accepting state).

• Each transition $q_{i-1} \stackrel{w_i}\to q_i$ corresponds to a transition of the word-NFA.

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

StackExchange Computer Science Q#109263, answer score: 9