Thompson Construction: Turning a Regular Expression into an Epsilon NFA

A regular expression is a description of a language written with three operators: concatenation, alternation, and Kleene star. The Thompson construction turns any such description into a nondeterministic automaton with empty transitions, and it does so compositionally: every subexpression becomes a machine with exactly one entry and one exit, and each operator connects smaller machines without touching their interiors.

That single invariant, one entry and one exit, is what makes the construction mechanical. It is also the reason the construction needs empty transitions at all, and understanding that requirement is more useful than memorizing the five diagrams.

The fragment invariant

A fragment is an NFA with a distinguished start state that has no incoming transitions and a distinguished accept state that has no outgoing transitions. Every state inside the fragment is reachable from the start and can reach the accept. The invariant is maintained by every rule, so the composition of fragments is again a fragment.

The rules are:

• Empty string. Two states, the start and the accept, joined by an empty transition. No symbol is consumed.
• Single symbol a. Two states joined by a transition labelled a.
• Concatenation rs. Build fragments for r and s. Add an empty transition from the accept of r to the start of s. The start of r is the new start; the accept of s is the new accept.
• Alternation r|s. Build both fragments. Add a new start with empty transitions to each fragment’s start, and a new accept with empty transitions from each fragment’s accept.
• Kleene star r*. Build the fragment for r. Add a new start and a new accept. Add an empty transition from the new start to the new accept (the zero-repetition path), an empty transition from the new start to r’s start, and empty transitions from r’s accept to both r’s start and the new accept.

The star rule is the only one that creates a cycle, and it creates it through empty transitions rather than symbol transitions. That distinction matters: a cycle of symbol transitions would let the machine loop without consuming input and never terminate, while a cycle of empty transitions is harmless because the simulation takes the closure of the live set rather than following paths one at a time.

Why the empty transitions exist

The alternative is to build the automaton by merging states: for concatenation, make the accept of r and the start of s the same state. That works and produces a smaller machine with no empty transitions. It fails as a general strategy for two reasons.

First, merging is not always possible. In alternation, the two branches need a common start; if the branches are built independently, each already has a start state, and merging them would require redirecting every incoming transition, which is exactly the work the extra state avoids. In star, the accept of r needs to loop back to its own start while also reaching the final accept; if r’s accept is also the overall accept, the loop would make the whole machine accept a prefix and keep going. Concatenation is the one case where merging works cleanly: r’s accept has no outgoing edge of its own, and making that state the start of s removes the need for any connecting edge at all.

Second, merging destroys the invariant that makes the construction compositional. If the accept of r becomes the start of s, then the accept of r has outgoing transitions and the start of s has incoming ones, so the fragment boundary is no longer identifiable. A compiler that builds the automaton bottom-up while parsing needs those boundaries stable: the parser holds a fragment, hands it to the parent rule, and the parent rewires only the two boundary states.

The price is states and transitions. Thompson’s construction produces at most 2n states for an expression of n symbols and operators, because each symbol contributes two states and each operator adds at most two. The standard count for transitions during the recursive construction is at most 4n including the empty transitions an operator inserts; the finished machine has strictly fewer, since concatenation adds one edge and every fragment’s exit state later gains an outgoing edge. An expression with 50 symbols and operators yields a machine of at most 100 states, small enough that a dense determinized table is plausible and a sparse one is certain to fit.

Building fragments from the parse tree

The construction is normally driven by a recursive-descent parser, with one function per grammar production. Each returns a fragment; the parent connects fragments and returns the composite.

class Frag:
    def __init__(self, start, accept, states, eps, sym):
        self.start, self.accept = start, accept
        self.states, self.eps, self.sym = states, eps, sym

def cat(a, b):
    a.eps[a.accept].append(b.start)          # the only new edge
    return Frag(a.start, b.accept, a.states | b.states,
                merge(a.eps, b.eps), merge(a.sym, b.sym))

def alt(a, b):
    s, f = new_state(), new_state()
    eps = merge(a.eps, b.eps)
    eps[s] = [a.start, b.start]
    eps[a.accept] = [f]
    eps[b.accept] = [f]
    return Frag(s, f, a.states | b.states | {s, f}, eps, merge(a.sym, b.sym))

def star(a):
    s, f = new_state(), new_state()
    eps = dict(a.eps)
    eps[s] = [a.start, f]                     # zero repetitions, or enter the loop
    eps[a.accept] = [a.start, f]              # repeat, or stop
    return Frag(s, f, a.states | {s, f}, eps, a.sym)

The concatenation rule adds exactly one edge, which is the strongest argument for the fragment invariant: composition is O(1) bookkeeping per operator, and the total work is linear in the size of the expression. The star rule adds two states and three edges, and alternation adds two states and four edges, so the state bound follows by induction over the syntax tree.

One detail is easy to get wrong. In star, the transition from the new start goes to the fragment’s start, not to its accept, and the accept of the fragment loops back to the fragment’s start rather than to the new start. Routing through the new start instead would make the new start reachable in the middle of the machine, which breaks the “no incoming transitions” half of the invariant and, in a one-pass simulation, changes which states are live.

From automaton to executable form

Two consumers take the fragment directly.

The first is the set-based simulator, which carries the epsilon closure of the live states and steps once per input symbol. The construction’s empty transitions become closure edges, and the machine runs in time proportional to the input length times the number of live states. That path is described in simulating an NFA without determinizing it, and it is the reason the empty transitions are cheap: a closure over an acyclic epsilon graph is a short walk, and even the cycles introduced by star are resolved by a fixed-point union.

The second is compilation to a small instruction set. Each state becomes an instruction, and the transition structure becomes control flow: a symbol transition becomes a “match this byte, else fail” instruction, an empty transition becomes an unconditional jump, and a state with two empty successors becomes a split. A star loop becomes a jump back to the split. The result is a program of a few instructions per state that a backtracking matcher can run directly, which is how many regular expression engines are built.

enum { CHAR, SPLIT, JMP, MATCH };
/* Compile one state of the Thompson NFA into one instruction. */
struct inst { int op; int x; int y; unsigned char c; };
/* SPLIT: try pc = x first, then pc = y. JMP: pc = x. CHAR: consume c. */

The instruction count equals the state count, so the 2n bound carries over: an expression of n symbols and operators compiles to at most 2n instructions. A backtracking engine exploring the split instructions without memoization can take exponential time on expressions with nested stars, which is the cost the set-based simulation avoids by tracking the union of live states instead of individual paths. Whether such a compiled machine accepts the same language as a reference pattern is a question answered by an equivalence check on the resulting automata, which compares two machines without requiring either to be minimized first.

Where the construction is wasteful, and why it is kept anyway

The machine produced by the construction has states that exist only to join fragments. For the expression abc, the construction yields six states, while a hand-built machine needs four. The extra states are eliminated by any determinization or minimization pass, so the waste is transient when the compilation step continues. Toolchains that stop at the NFA and simulate it pay for the extra states in every closure computation.

There is a second kind of waste that matters more for large expressions: nested alternations produce chains of empty transitions that a closure must traverse. A closure computed by a fixed-point union over a long chain costs one pass over the live set per level in the worst case, which is why simulators precompute closures per state or cache them per set.

The construction is kept because it is total and syntax-directed. There is no case analysis over the shape of the expression, no need to detect when a subexpression can match the empty string, and no global reasoning: each rule is local, and the invariant survives every combination. Constructions that avoid empty transitions, such as the derivative-based one, achieve smaller machines but require normalizing the expression at each step, and that normalization is where their complexity lives.

A final property is worth stating because it is what licenses the whole construction. The construction preserves the language exactly: the fragment for r accepts precisely the strings in L(r), with empty transitions contributing nothing to the consumed input. Since the machine is nondeterministic, the question of whether a string is accepted becomes a question about reachability, which the subset simulation answers, and the determinized version answers with a table lookup per symbol.