9
$\begingroup$

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.

enter image description here

$\endgroup$
10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$ $\endgroup$ – Convex Leopard May 12 at 19:22
  • 1
    $\begingroup$ Yes, that’s a nice description. $\endgroup$ – Yuval Filmus May 12 at 19:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.