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))Line by line
NFA.state()hands out numbered states, andedgesholds moves as (from, symbol, to);Nonestands for ε.union,concat,starandatommirror the precedence levels, so(a|b)*abbis grouped as ((a|b)*)·a·b·b.starwraps a fragment with a new start and end and four ε-moves: skip, enter, repeat and leave.matchessimulates the NFA with ε-closures and accepts when the final set contains the end state.- The printed counts show the NFA's size, and each test word gives the same answer as
re.fullmatchwould: 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 repeatab. - Reusing states between fragments: every fragment needs its own fresh states.
- Forgetting the skip move in star, so R* fails to match ε.
- Letting
concatread 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.fullmatchon 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
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.