NFA vs DFA
Thompson's construction turns a pattern into an NFA in linear space; subset construction turns the NFA into a DFA that runs in linear time. The bill for that speed is table size, and in the worst case it is exponential.
Why build an NFA and then convert it, instead of building the DFA directly?
Two machines for the same set of strings. An NFA state set is "every place the match could be right now"; a DFA state is "the one place it is". Converting between them is the act of trading a per-character set of possibilities for a per-character single index — which is the whole reason a generated scanner has no inner-loop branching.
Subset construction preserves the recognised language exactly: a DFA state is an NFA state set, and it accepts precisely when that set contains an accepting NFA state. It preserves nothing else — the NFA's structural correspondence to the source pattern is destroyed, which is why a minimised DFA cannot tell you which sub-pattern matched unless accepting states were tagged before the construction.
Key points
- Thompson's construction builds an NFA compositionally, linear in the size of the pattern, using epsilon transitions to glue fragments.
- Subset construction makes each DFA state a set of NFA states, eliminating both nondeterminism and epsilon moves.
(a|b)*abbhas an eleven-state NFA and a five-state DFA — the standard worked example, checkable by hand.- A DFA can need exponentially many states; "the k-th symbol from the end is
a" needs at least 2^k. - Programming-language token sets do not hit that case, which is why generated lexers determinise eagerly.
- General-purpose engines such as RE2 build the DFA lazily under a memory cap and fall back to NFA simulation, bounding the worst case.
- Rule priority is resolved at construction time, not at scan time, which is why the generated inner loop is branch-free.
- Minimisation must run after accepting states are tagged with kind and priority, or it merges states that should stay distinct.
Regex to NFA: Thompson's construction
Thompson's construction builds an NFA from a pattern compositionally: each regular-expression operator has a fixed wiring, and the pieces are glued with epsilon transitions — moves the machine may take without consuming input. A single character is two states and one labelled edge. An alternation is a new start with epsilon edges to both branches and a new accept both branches reach. A concatenation joins one fragment's accept to the next's start. A star adds an epsilon loop and an epsilon bypass.
The critical property is size: the resulting NFA has at most a constant number of states per input symbol, so it is linear in the pattern length. That is why compiling a pattern is cheap even when the pattern is large, and it is why an NFA simulation is a viable strategy in its own right — RE2 and Go's regexp simulate the NFA directly, tracking a set of active states, which costs more per character and guarantees no exponential blowup anywhere.
Epsilon transitions are what make the construction compositional, and they are also what the next step has to eliminate. A machine that can move without consuming input cannot be driven by a simple table lookup, because "the current state" is not a single value.
| Pattern | Construction | States added |
|---|---|---|
a (a single character) | Two states, one edge labelled a | 2 |
ε (empty) | Two states, one epsilon edge | 2 |
R | S | New start with epsilon edges into R and S; both accepts epsilon into a new accept | 2 |
R S | R's accept becomes S's start | 0 |
R* | New start and accept, epsilon bypass, epsilon loop from R's accept back to R's start | 2 |
R+ | R R*, or a loop without the bypass | 2 |
NFA to DFA: subset construction
Subset construction, also called the powerset construction, makes a DFA whose states are *sets* of NFA states. Start with the epsilon-closure of the NFA start — every state reachable without consuming anything — and call that DFA state A. For each input symbol, compute where every NFA state in A could go, take the epsilon-closure of the result, and that set is another DFA state. Repeat until no new sets appear.
The worked example below is the classic one: (a|b)*abb, the pattern "any string of as and bs ending in abb". Its Thompson NFA has eleven states numbered 0 to 10, with 10 accepting. Subset construction produces exactly five DFA states, and the table is small enough to check by hand — which is worth doing once, because the mechanics never get harder than this.
Notice that every DFA state has a transition on both a and b, and that no state has two transitions on the same symbol. That is determinism, and it is what makes the scan a table lookup rather than a set update. Notice also that the NFA state sets overlap heavily: states 1, 2, 4, 6 and 7 appear in almost every row, because the (a|b)* prefix means the match can always restart.
(a|b)*abb — five DFA states from eleven NFA states| DFA state | NFA state set | on `a` | on `b` | Accepting? |
|---|---|---|---|---|
| A (start) | {0, 1, 2, 4, 7} | B | C | no |
| B | {1, 2, 3, 4, 6, 7, 8} | B | D | no |
| C | {1, 2, 4, 5, 6, 7} | B | C | no |
| D | {1, 2, 4, 5, 6, 7, 9} | B | E | no |
| E | {1, 2, 4, 5, 6, 7, 10} | B | C | yes — 10 is in the set |
The exponential case is real, and bounded in practice
A DFA state is a subset of NFA states, and a machine with n NFA states has 2^n possible subsets. Usually only a handful are reachable — five out of a possible 2048 in the example above — but there are patterns for which almost all of them are.
The standard family is "the k-th symbol from the end is a", written (a|b)*a(a|b)(a|b)…(a|b) with k-1 trailing wildcards. Recognising it requires remembering the last k symbols, so any DFA needs at least 2^k states, while the NFA needs about k. At k = 20 that is a million states; at k = 30 it is a billion, and the construction does not finish.
For programming-language token sets this does not happen. Token patterns are shallow, mostly disjoint, and anchored at the start, so the reachable subset count stays close to the NFA state count — a typical language's merged scanner is a few hundred to a few thousand DFA states. This is why generated lexers can rely on full determinisation while general-purpose regex libraries cannot: a lexer's patterns are written by a language designer, and a library's patterns are written by whoever calls it.
The libraries that must handle arbitrary patterns choose accordingly. RE2 and Go's regexp build the DFA *lazily*, constructing states on demand and evicting them under a memory cap, falling back to NFA simulation if the cap is hit. That gives DFA speed on ordinary patterns and a hard bound on pathological ones, which is exactly the engineering answer to an exponential worst case.
| NFA simulation | Eager DFA | Lazy DFA | |
|---|---|---|---|
| Construction cost | None beyond the NFA | Exponential worst case | Paid per state actually reached |
| Per-character cost | Update a state set | One table lookup | One lookup, plus a miss on first visit |
| Memory | O(pattern size) | O(DFA size), unbounded | Capped, with eviction |
| Worst-case time | Linear in input × pattern | Linear in input | Linear in input |
| Used byimplementation | RE2 fallback, Thompson's 1968 paper | flex, re2c, generated lexers | RE2, Go regexp |
Minimisation, and what it destroys
A DFA produced by subset construction is usually not minimal — several states may be indistinguishable in the sense that no input string leads one to accept and the other to reject. Hopcroft's algorithm merges them in O(n log n) by repeatedly partitioning states that behave differently on some symbol, and the result is the unique smallest DFA for the language.
Minimisation is worth doing when table size matters, and it has a cost that is easy to overlook: it destroys the correspondence between DFA states and the patterns they came from. Before minimisation you can often tell which rule a state belongs to; afterwards, a single state may serve five patterns. This is why accepting states must be *tagged with their token kind and priority before* minimisation runs — the tag becomes part of what makes two states distinguishable, so states accepting different kinds are never merged.
That is also the mechanism by which rule priority survives determinisation. When subset construction produces a DFA state whose NFA set contains two accepting states — say, both the keyword pattern and the identifier pattern — the generator resolves it once, at construction time, by the declared priority. Nothing is decided at scan time, which is why the inner loop has no conditionals in it at all.
How it works
The steps, in the order the compiler takes them.
- Build an NFA fragment per regular-expression operator and glue them with epsilon transitions — Thompson's construction.
- Tag each pattern's accepting state with its token kind and its priority before doing anything else.
- Compute the epsilon-closure of the NFA start state; that set is the DFA start state.
- For each unprocessed DFA state and each input symbol, compute the set of NFA states reachable on that symbol, take its epsilon-closure, and add it as a DFA state if new.
- Mark a DFA state accepting if its NFA set contains any tagged accepting state; if it contains several, resolve by priority now.
- Minimise with Hopcroft's algorithm, treating states accepting different kinds as initially distinguishable.
- Emit the transition table over character classes, plus the accepting-kind array indexed by state.
How it breaks
What the engineer observes when it goes wrong — not what goes wrong internally.
- Accepting states are tagged after minimisation, so the keyword and identifier states are merged and every keyword lexes as an identifier — the parser then reports errors on perfectly ordinary code.
- A pattern set hits the exponential case and the generator runs for minutes or exhausts memory, with an error that names an internal table rather than the offending pattern.
- Epsilon-closure is computed once at the start rather than after every move, so patterns that begin with an optional group silently fail to match when the optional part is absent.
- A backtracking engine is used where a DFA was assumed, and a service that lexes user-supplied input hangs on a crafted request — the process pins a core and stops responding.
- Rule priority is left undeclared, the generator picks arbitrarily, and reordering unrelated rules in the specification changes which token a given input produces.
When it helps
- Building a lexer generator, or understanding the output of one — the state counts flex reports are exactly the result of this pipeline.
- Choosing a regex engine under adversarial input, where the difference between simulation, eager DFA and lazy DFA is a security property.
- Diagnosing a generator that will not terminate: recognising the exponential family in a pattern is usually enough to rewrite it.
When it hurts
- For a token set of a dozen patterns, the whole pipeline is invisible machinery — a hand-written switch does the same job and is easier to give good diagnostics from.
- When patterns are dynamic and used once, eager determinisation is wasted work: NFA simulation matches faster overall because construction dominates.
What it costs
Every one of these is paid by something.
- Eager determinisation buys a branch-free constant-work inner loop and costs construction time plus table memory, unbounded in the worst case.
- NFA simulation buys a hard linear bound with no construction and costs a set update per character, which is several times slower on ordinary input.
- Lazy determinisation buys both bounds and costs implementation complexity plus a cache that can thrash — a pathological pattern degrades to NFA speed rather than failing, which is a behaviour change under load.
- Minimisation buys a smaller table and better cache behaviour, and costs the debuggability of the generated scanner because states no longer correspond to patterns.
What else you could do
What a different compiler or language does instead, and when that is better.
- Simulate the NFA directly, tracking the active state set. This is Thompson's 1968 algorithm, it never blows up, and it is what RE2 falls back to — see
[[regular-languages]]. - Backtracking, which is what PCRE, Java, Python and JavaScript engines do. It buys backreferences and lookaround and gives up the linear bound entirely.
- A bit-parallel simulation such as the shift-or algorithm, which represents the active NFA state set as a machine word and advances it with a shift and a mask. Extremely fast for patterns that fit in a word, and limited to exactly that.
- Skip the automata entirely and hand-write the scanner, encoding the states in control flow. This is what production compilers do, and it trades construction guarantees for diagnostics and tunability — see
[[lexer-implementation]].
See it for yourself
The flag, dump or tool that shows you this directly.
flex -v grammar.lprints the NFA and DFA state counts for your rules, which is this construction reporting on itself.re2c --emit-dot patterns.re | dot -Tsvgrenders the constructed automaton so you can count the states directly.- Go's
regexp/syntaxpackage will parse a pattern to a syntax tree and compile it to a program you can print, which shows the NFA instruction form RE2 simulates. - Try the exponential family: give flex a pattern for "the twentieth character from the end is
a" and watch the reported DFA state count against a pattern for "starts witha". - Compare engines on
(a+)+bagainst thirtyas: Go'sregexpreturns immediately, Python'sredoes not.
Plausible wrong readings
Stated the way a confident engineer states them.
- "An NFA is slower than a DFA." Per character, yes. End to end, an NFA simulation can win, because the DFA had to be constructed first and construction can dominate or fail.
- "Subset construction always blows up." It blows up on a specific family of patterns. Programming-language token sets are not in it, which is why eager determinisation is standard for lexers.
- "Nondeterministic means the machine guesses." It means several states are active at once. The simulation tracks all of them; nothing is guessed and nothing is random.
- "Minimisation is always worth it." It shrinks the table and destroys the state-to-pattern correspondence, which makes a generated scanner considerably harder to debug.
Misconceptions
The claim, and what is actually true.
Go deeper
The same idea at increasing depth. Stop wherever it stops being useful.
overview
A pattern becomes an NFA — a machine that can be in several states at once — by a mechanical wiring rule per operator. That NFA becomes a DFA by making each DFA state stand for a set of NFA states, so only one is active at a time. The DFA matches with one table lookup per character; the conversion is what paid for that.
practical
For a lexer, determinise eagerly: token patterns do not hit the exponential case, and a branch-free inner loop is worth the construction. For matching patterns you did not write, against input you do not control, use an engine with a linear guarantee — RE2 or Go's regexp — because a backtracking engine on (a+)+b is a denial-of-service surface. And tag accepting states with kind and priority before minimising, or the minimiser will merge your keywords into your identifiers.
advanced
The three strategies are really points on one curve: how much of the DFA do you build, and when. Eager construction builds all of it before any input arrives, which is right when the pattern is fixed and the input volume is large — a compiler lexer, run millions of times on the same grammar. NFA simulation builds none of it, which is right when the pattern is used once. Lazy construction builds the reachable part on demand and caps it, which is right when neither the pattern nor the input is known in advance. RE2 exists because Google needed to run user-supplied patterns over large corpora and could not accept either an exponential construction or an exponential match, and the lazy DFA is the design that satisfies both constraints simultaneously. The compiler case is easy precisely because the pattern set is trusted and fixed, and that is worth noticing: the reason lexer generators can be simple is a property of their deployment, not of their theory.
How much this depends on
Nothing in this domain is true of every compiler. These say how much.
regexp as of current releases; when the cache is exhausted they fall back to NFA simulation rather than failing. flex and re2c determinise eagerly at generation time and would simply not finish on a pathological pattern set. Python's re and PCRE backtrack and have neither bound.flex -v is how you would find out rather than assuming.If you were asked this in an interview
- Walk me through subset construction on a small NFA. What is a DFA state, exactly?
- When would you simulate the NFA instead of determinising it?
- Give me a pattern family whose DFA is exponentially larger than its NFA, and say why lexers do not hit it.