NFA → DFA: Subset Construction

The NFA simulator from the previous lesson is fast enough — O(n·m) is linear in text. But the inner loop recomputes the same move + closure over and over for any pattern run on multiple inputs. Real engines (RE2, Go's regexp) precompute these transitions into a DFA.

A DFA (Deterministic Finite Automaton) has exactly ONE transition per (state, char) pair. No nondeterminism, no epsilon closure at run-time — just look up the next state in a table. Per-character cost: O(1).

Subset construction

Each DFA state is a subset of NFA states (specifically, an ε-closure-closed subset). The algorithm:

start_dfa = ε-closure({nfa_start})
worklist  = [start_dfa]
while worklist not empty:
    S = worklist.pop()
    for each char c in the alphabet:
        T = ε-closure(move(S, c))
        if T is empty: skip
        if T not seen: assign new DFA id, add to worklist
        add transition S --c--> T
A DFA state is accepting if its subset contains the NFA accept state.

Worked example: a|b

NFA (Thompson):

0 --ε--> 1 --a--> 2 --ε--> 5  (accept)
0 --ε--> 3 --b--> 4 --ε--> 5

DFA subsets:

• D0 = closure({0}) = {0, 1, 3}
• on 'a': move({0,1,3}, 'a') = {2}, closure = {2, 5} = D1 (ACCEPT)
• on 'b': move({0,1,3}, 'b') = {4}, closure = {4, 5} = D2 (ACCEPT)

DFA:

D0 --a--> D1 (ACCEPT)
D0 --b--> D2 (ACCEPT)

Notice the DFA is tiny — 3 states for what was a 6-state NFA, and matching is a single table lookup per char.

State explosion

The pathological case: NFA with N states can produce 2^N DFA states. In practice this rarely hits — most regexes produce DFAs proportional to the NFA. But it's why RE2 builds the DFA lazily, on demand, discarding rarely-used states under a memory budget.

Why bother?

• Speed: DFA matching has the tightest inner loop possible — single array lookup per byte. ~5 GB/s on a modern CPU for compiled patterns.
• Determinism: same input → same time. No backtracking.
• Predictability: linear in text, full stop.

The trade-off: backreferences and lookaround break the DFA model, so RE2 refuses them entirely. That's why Go's regexp is so fast — and why it rejects \1.