2.4 NFA and Epsilon-NFA

A nondeterministic finite automaton, or NFA, relaxes the DFA rule that each state and input symbol determine exactly one next state. An NFA may have zero, one, or many transitions for the same symbol. When it reads input, it can conceptually explore many possible paths at the same time.

This does not mean an implementation must magically guess the right path. We can simulate an NFA by maintaining a set of active states. After each input symbol, all active states contribute their possible next states. If at least one path consumes the whole input and ends in an accepting state, the NFA accepts.

The acceptance rule is existential:

An NFA accepts w if there exists at least one accepting path for w.

Failed paths do not matter if another path succeeds. This is the main mental shift from DFA execution.

Why NFAs Are Useful

NFAs and DFAs recognize the same class of languages: the regular languages. NFAs are not more powerful, but they are often easier to construct. Regular-expression operators map naturally to small NFA fragments:

• Union creates a branch.
• Concatenation connects one fragment to another.
• Kleene star creates a loop and an exit.
• Optional pieces become a branch that skips the fragment.

This construction style is extremely useful in lexer generators. It is easier to build an NFA from many token regular expressions, then convert the combined NFA into a DFA for fast scanning.

Subset Construction

To convert an NFA to a DFA, each DFA state represents a set of NFA states. The start DFA state is the set containing the NFA start state, possibly extended by epsilon-closure if epsilon transitions exist. For each input symbol, we compute where the NFA could go from any state in the set. That resulting set becomes a DFA state.

For a simple NFA without epsilon transitions:

DFA state S = {q0, q2}
on symbol a:
    move(q0, a) = {q1}
    move(q2, a) = {q2, q3}
therefore:
    δ_DFA(S, a) = {q1, q2, q3}

If any NFA state inside a DFA-state set is accepting, the corresponding DFA state is accepting. This preserves the NFA's existential acceptance rule: at least one active NFA path has succeeded.

Subset construction can produce up to 2^n DFA states for an NFA with n states. In practice, many subsets are unreachable, and minimization can reduce the result. Still, this possible blowup is one reason lexer generators care deeply about implementation engineering.

Epsilon Transitions

An epsilon transition, written ε, moves from one state to another without consuming an input symbol. An automaton with these transitions is often called an ε-NFA.

Epsilon transitions are useful glue. Suppose a regex has a union a | b. A Thompson-style NFA can create a new start state with epsilon edges to the a fragment and the b fragment. No input has been consumed yet; the automaton has merely chosen which branch may match. For r*, epsilon edges allow the automaton to enter the loop, repeat it, or skip it entirely.

The epsilon-closure of a state is the set of all states reachable from it by following zero or more epsilon transitions. It always includes the original state because taking zero transitions is allowed.

For a set of states, the closure is the union of each state's closure:

ε-closure({A, C}) = ε-closure(A) ∪ ε-closure(C)

When simulating an epsilon-NFA, we must include epsilon-closure before consuming input and after each move. Otherwise the simulation misses states that are reachable for free.

Nondeterminism Is a Construction Tool

An NFA does not choose one branch at runtime in the human sense. It accepts when some path consumes the whole input and reaches an accepting state. Epsilon transitions consume no symbol; their closure is the set of all states reachable for free. To simulate an epsilon-NFA on one character, take epsilon-closure, follow every matching edge, then take epsilon-closure again.

For a regex union r|s, Thompson construction creates a fresh start with epsilon edges to the starts of r and s, and a fresh accept reached by epsilon from both ends. Concatenation joins one accept to the next start by epsilon; star adds routes that skip or repeat the submachine. This is wonderfully mechanical, which is why NFAs are preferred during construction even though deterministic scanners are preferred during execution.

Avoid Two Common Errors

• Epsilon is not an input character. It changes reachable states without advancing the cursor.

• Multiple active states do not require exponential runtime when represented as a bitset; subset construction turns each reachable set into one DFA state ahead of time.