From regular expression to NFA: Thompson's construction

Advanced

Introduction

How does a computer run a regular expression? One answer, published by Ken Thompson in 1968 and still used today, is to compile the expression into an ε-NFA and then simulate it. The construction is short, mechanical and safe: the NFA has at most about twice as many states as the expression has characters, and matching never takes exponential time. Building it yourself shows exactly how expressions and automata are the same thing.

How it works

The construction builds a fragment for each part of the expression: a small NFA with exactly one start state and one end state.

  • Symbol c: two new states s and e with one move s --c--> e.
  • Concatenation RS: an ε-move from the end of R's fragment to the start of S's.
  • Union R|S: a new start with ε-moves to both fragments' starts, and ε-moves from both ends to a new end.
  • Star R*: a new start and end; ε-moves let the machine skip R entirely (start to end), enter it (start to R's start), and repeat it (R's end back to R's start, or on to the end).

To build fragments in the right order, the expression is parsed with respect to precedence. A recursive-descent parser has one function per level: union calls concat, concat calls star, and star calls atom, which reads a symbol or a bracketed expression by calling union again. Each function returns the start and end of the fragment it built.

Another common approach first inserts an explicit concatenation operator (ab becomes a.b), converts the expression to postfix with the shunting-yard algorithm (a.b|c becomes ab.c|), and then builds fragments with a stack. Both approaches produce the same kind of NFA.

Once built, the NFA is run exactly as in the NFA lesson: keep the set of current states, take ε-closures, and accept if the end state is in the final set.

Syntax

def union():            # R | S | ...
def concat():           # R S ...
def star():             # R * ...
def atom():             # symbol, or ( union )
# each returns (start, end) of the fragment it built

Example

class NFA:
    def __init__(self):
        self.edges = []
        self.count = 0

    def state(self):
        self.count += 1
        return self.count - 1


def build(regex):
    nfa = NFA()
    pos = 0

    def peek():
        return regex[pos] if pos < len(regex) else None

    def take():
        nonlocal pos
        pos += 1
        return regex[pos - 1]

    def union():
        start, end = concat()
        while peek() == "|":
            take()
            s2, e2 = concat()
            s, e = nfa.state(), nfa.state()
            nfa.edges += [(s, None, start), (s, None, s2), (end, None, e), (e2, None, e)]
            start, end = s, e
        return start, end

    def concat():
        start = end = nfa.state()
        while peek() not in (None, "|", ")"):
            s2, e2 = star()
            nfa.edges.append((end, None, s2))
            end = e2
        return start, end

    def star():
        start, end = atom()
        while peek() == "*":
            take()
            s, e = nfa.state(), nfa.state()
            nfa.edges += [(s, None, start), (s, None, e), (end, None, start), (end, None, e)]
            start, end = s, e
        return start, end

    def atom():
        if peek() == "(":
            take()
            result = union()
            take()
            return result
        s, e = nfa.state(), nfa.state()
        nfa.edges.append((s, take(), e))
        return s, e

    start, end = union()
    return nfa, start, end


def matches(regex, word):
    nfa, start, end = build(regex)

    def closure(states):
        seen, stack = set(states), list(states)
        while stack:
            s = stack.pop()
            for a, symbol, b in nfa.edges:
                if a == s and symbol is None and b not in seen:
                    seen.add(b)
                    stack.append(b)
        return seen

    current = closure({start})
    for c in word:
        current = closure({b for a, symbol, b in nfa.edges if a in current and symbol == c})
    return end in current


nfa, start, end = build("(a|b)*abb")
print("states:", nfa.count, "moves:", len(nfa.edges))
for w in ["abb", "aabb", "ab", "babb", ""]:
    print(w or "ε", matches("(a|b)*abb", w))
Open in compiler

Line by line

  1. NFA.state() hands out numbered states, and edges holds moves as (from, symbol, to); None stands for ε.
  2. union, concat, star and atom mirror the precedence levels, so (a|b)*abb is grouped as ((a|b)*)·a·b·b.
  3. star wraps a fragment with a new start and end and four ε-moves: skip, enter, repeat and leave.
  4. matches simulates the NFA with ε-closures and accepts when the final set contains the end state.
  5. The printed counts show the NFA's size, and each test word gives the same answer as re.fullmatch would: abb, aabb and babb end in abb; ab and ε do not.

Expected result

states: 17 moves: 19
abb True
aabb True
ab False
babb True
ε False

In the real world

Thompson's construction is at the heart of grep, RE2 (used by Google's code search and by Go's regexp package) and Rust's regex crate. Because they simulate an NFA instead of backtracking, they match in time linear in the input, which protects servers from "catastrophic backtracking" attacks. Lexer generators use the same construction before converting to a DFA.

Common mistakes

  • Ignoring precedence: parse union, then concatenation, then star, or ab* will repeat ab.
  • Reusing states between fragments: every fragment needs its own fresh states.
  • Forgetting the skip move in star, so R* fails to match ε.
  • Letting concat read a ) or |: those end the current fragment.

Best practices

  • Write one parser function per precedence level, each returning (start, end).
  • Test the parser on single symbols, then on each operator alone, then on combinations.
  • Compare your matcher with re.fullmatch on many short strings.

Summary

Thompson's construction turns each piece of a regular expression into an NFA fragment with one start and one end: a single move for a symbol, ε-links for concatenation, and two new states with four ε-moves for union and star. Parsing with recursive descent builds the fragments in precedence order. Simulating the resulting NFA matches strings in linear time, and the construction proves that every regular expression describes a regular language.

Quick check

1. In Thompson's construction, what does a single symbol c become?
2. Which moves does the star fragment need so that R* accepts ε?
3. Why parse with one function per precedence level?
4. What is ab.c| in postfix written normally?

Key takeaways

  • Each piece of a regex becomes a fragment with one start and one end state.
  • Union and star add two new states and four ε-moves; concatenation links fragments with ε-moves.
  • Simulating the NFA with sets of states matches in time proportional to the regex size times the text length.

Practice problems for this lesson

My notes

Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.