Thompson's Construction (RE → NFA)

We can write a token as a regular expression and we can run a token recogniser as a finite automaton. The bridge from one to the other is Thompson's construction (Ken Thompson, 1968): a mechanical, syntax-directed recipe that turns any regular expression into an \varepsilon-NFA recognising the same language. It is beautiful because it is compositional — it builds the NFA for a big expression by gluing together the NFAs for its parts, one small, uniform fragment per operator, following the structure of the regex exactly as a parser would.

The one invariant that makes it work

Every fragment Thompson builds obeys a single, rigid shape, and this discipline is the whole trick:

Each NFA fragment has exactly one start state and exactly one accept state.
The accept state has no outgoing transitions (it is a clean "output socket").
No transition ever enters the start state from outside (it is a clean "input socket").

Because every fragment looks the same from the outside — one wire in, one wire out — fragments plug into each other with \varepsilon-transitions like Lego bricks, and the invariant is preserved at every step. That uniformity is why the construction is so short and why its correctness is easy to prove by induction on the structure of the regular expression.

Base cases

The recursion bottoms out on the two smallest expressions:

For \varepsilon: a start state and an accept state joined by a single \varepsilon-transition, i \xrightarrow{\varepsilon} f.
For a single symbol a: a start and an accept joined by one a-transition, i \xrightarrow{a} f.

Each uses two brand-new states, so each base case adds exactly two states. Everything larger is these atoms wired together.

The three inductive rules

Given fragments N(r) and N(s) that already satisfy the invariant, the operators combine them by adding new states and \varepsilon-edges only:

Union r \mid s. Add a new start i with \varepsilon-edges to the starts of N(r) and N(s), and a new accept f reached by \varepsilon-edges from both their accepts. Two new states.
Concatenation r\,s. Merge the accept of N(r) with the start of N(s) (an \varepsilon-edge, or a direct identification). No new states — the start of the whole is N(r)'s start, the accept is N(s)'s accept.
Closure r^{*}. Add a new start i and new accept f, with four \varepsilon-edges: i \to start of N(r) (enter the loop), accept of N(r)\to i's inner start again — more precisely accept of N(r) \to start of N(r) (repeat) and accept of N(r) \to f (exit), plus i \to f (match zero copies). Two new states.

The optional r? and positive closure r^{+} are just sugar: r? = r \mid \varepsilon and r^{+} = r\,r^{*}, so they reduce to the three rules above.

Watch it grow: building (a\mid b)^{*}

Nothing beats seeing the fragments snap together. Below we build the NFA for (a\mid b)^{*} in the exact order Thompson's construction dictates: the two symbol atoms first, then the union that joins them, then the closure that wraps the lot. Step through it and watch the single-start / single-accept invariant hold at every stage.

Count the states at the end: two for each symbol atom (4), two for the union's new start/accept (6), two for the closure's new start/accept (8). Every join was an \varepsilon-edge; no atom's internals were ever disturbed. That is the signature of the construction — it only ever adds around existing fragments.

The construction in code

Because each rule just allocates a couple of states and some \varepsilon-edges, the whole thing is a handful of functions over a shared state counter. Below, a Frag is a { start, accept } pair; the combinators build fragments and we read off the total state count for (a\mid b)^{*}abb.

type Frag = { start: number; accept: number }; type Edge = { from: number; to: number; sym: string }; // sym "eps" = ε let next = 0; const edges: Edge[] = []; const newState = () => next++; const link = (from: number, to: number, sym: string) => edges.push({ from, to, sym }); // base case: a single symbol function symbol(sym: string): Frag { const s = newState(), a = newState(); link(s, a, sym); return { start: s, accept: a }; } // concatenation: r then s (ε-glue r.accept -> s.start) function concat(r: Frag, s: Frag): Frag { link(r.accept, s.start, "eps"); return { start: r.start, accept: s.accept }; } // union: r | s (new start and accept, four ε-edges) function union(r: Frag, s: Frag): Frag { const i = newState(), f = newState(); link(i, r.start, "eps"); link(i, s.start, "eps"); link(r.accept, f, "eps"); link(s.accept, f, "eps"); return { start: i, accept: f }; } // closure: r* (new start and accept, enter/repeat/skip/exit ε-edges) function star(r: Frag): Frag { const i = newState(), f = newState(); link(i, r.start, "eps"); // enter link(r.accept, r.start, "eps"); // repeat link(i, f, "eps"); // skip (zero copies) link(r.accept, f, "eps"); // exit return { start: i, accept: f }; } // Build (a|b)*abb const ab = union(symbol("a"), symbol("b")); const nfa = concat(concat(concat(star(ab), symbol("a")), symbol("b")), symbol("b")); console.log("start state:", nfa.start, " accept state:", nfa.accept); console.log("total states:", next); // 11 — the Dragon Book's number console.log("total edges :", edges.length); console.log("ε-edges :", edges.filter((e) => e.sym === "eps").length);

Run it: exactly 11 states for (a\mid b)^{*}abb — the very machine the subset construction later collapses to five DFA states. The construction never backtracks and never inspects the fragments it combines; it just wires new states around them.

Why it is correct — and cheap

Correctness. For every regular expression r, the NFA N(r) accepts exactly the language L(r) — proved by induction on the structure of r, the base cases and three rules being the inductive steps.
Size. N(r) has at most 2|r| states and O(|r|) transitions, where |r| counts the symbols and operators of r — the NFA is linear in the size of the expression.
Bounded branching. Every state has at most two outgoing transitions, and every state has at most one outgoing non-\varepsilon edge — a tidy shape that makes later simulation and subset construction easy.

Linear size is what makes the whole scanner pipeline practical: a regex of length n becomes an NFA of O(n) states, and only the subsequent DFA conversion can (rarely) blow up.

You can — the "McNaughton–Yamada" or followpos method builds a DFA straight from the regex's syntax tree, and lex uses a variant of it. But Thompson's route is prized for its simplicity and its speed of construction: it is linear-time, dead simple to implement correctly, and it is the beating heart of fast regex engines like Russ Cox's RE2 and Go's regexp, which simulate the NFA directly (tracking a set of states) to guarantee linear-time matching with no catastrophic backtracking. Thompson's 1968 paper literally compiled a regex into IBM 7094 machine code, one instruction block per fragment — the same compositional idea, sixty years young.

The commonest way to wreck the construction is to break the fragment invariant:

Do not let a fragment have two accept states. In the union r \mid s, resist the temptation to just declare "accept if you reach either branch's accept". You must funnel both branch-accepts into one new accept via \varepsilon-edges, or the enclosing closure/concatenation will have two sockets to wire and the recursion falls apart.
Do not reuse or delete inner states when concatenating. Concatenation glues r's accept to s's start with an \varepsilon-edge; the inner states keep their identities. Merging them "to save a state" is how you accidentally create a back-edge that changes the language.
Closure needs all four \varepsilon-edges. Forget the i \to f "skip" edge and r^{*} can no longer match the empty string; forget the accept-to-inner-start "repeat" edge and it matches at most one copy. Each edge encodes one clause of "zero or more".