Lesson 1.1 — Regular languages, regular expressions and Thompson's construction¶
Techniques: regular expressions and Kleene's theorem (closure properties, the pumping lemma), Thompson's construction (McNaughton–Yamada–Thompson), the position automaton (Glushkov, McNaughton–Yamada, Berry–Sethi) · Pebble implements: Thompson's construction as the front half of every engine in the regex lab · Prerequisites: none (sets, induction) · Time: 4–6 hours
Every token of Pebble is described by a pattern. An identifier is a letter or _ followed by letters, digits and _; a hexadecimal literal is 0x followed by a hex digit and then hex digits or _. In regular-expression notation:
A lexer generator (flex, re2c) reads a list of such patterns and produces a program that splits a file into tokens. This lesson answers the first half of the question "how?": what patterns can say, why they are the right language for tokens, and how to turn a pattern into a machine, a nondeterministic finite automaton, in time linear in the pattern. The running example of the whole chapter is the textbook pattern
the language of strings over \(\{a, b\}\) that end in \(abb\) [Dragon2 §3.7].
1. Problem and motivation¶
A lexer must decide, for each prefix of the remaining input, whether it can be a token of each kind. We need (1) a notation for token classes that is precise and closed under the operations a language designer uses (alternatives, sequences, repetition), and (2) an algorithm that turns the notation into something that runs in time linear in the input. The notation is the regular expression, and the machine is the finite automaton. pebblec's hand-written lexer (exercises E1–E5) is a finite automaton written as code; the lab builds automata from expressions mechanically.
Regular expressions and closure properties¶
Kleene introduced regular events, and the expressions that denote them, in a 1951 RAND memorandum published in 1956 [Kle56], to describe what McCulloch–Pitts nerve nets can recognize. His theorem, that regular expressions and finite automata describe the same languages, is why lexer generators work: a token specification can be compiled to an automaton, and an automaton can be read back as an expression. Closure properties matter in practice: if every token class is regular, then "any keyword", "an identifier that is not a keyword" (difference), and "the longest token at this position" are regular too. The limits matter as well. Pebble's nested block comments /* a /* b */ c */ are not a regular language (Corollary 1.1.17), so no pattern can describe them, and Pebble's lexer keeps a depth counter instead.
Thompson's construction¶
Ken Thompson built regular-expression search into the QED editor and published the method in 1968 [Tho68]: compile the expression, piece by piece, into a nondeterministic automaton (in his paper, directly into IBM 7094 machine code) and simulate all its states at once. McNaughton and Yamada had given a construction from expressions to state graphs in 1960 [MY60]. The textbook form used here, which the Dragon book calls the McNaughton–Yamada–Thompson (MYT) construction [Dragon2 §3.7.4], builds one small fragment per operator. Every modern automata-based engine starts this way: RE2, Go's regexp, Rust's regex-automata and the lab's four back ends.
The position automaton¶
Glushkov [Glu61] and McNaughton–Yamada [MY60] observed that one can skip ε-edges entirely: number the symbol occurrences ("positions") of the expression, and let the automaton's states be the positions themselves. Berry and Sethi [BS86] rederived it with derivatives. The result has exactly one state per symbol occurrence plus a start state, no ε-edges, and it is the basis of the "followpos" DFA construction in the Dragon book [Dragon2 §3.9] and of GNU grep's matcher (lib/dfa.c).
2. Definitions and algorithms¶
Definition 1.1.1 (Alphabet, words, languages)
An alphabet \(\Sigma\) is a finite nonempty set of symbols. A word over \(\Sigma\) is a finite sequence \(w = a_1 a_2 \cdots a_n\) with \(a_i \in \Sigma\); its length is \(\lvert w \rvert = n\), and the empty word is \(\varepsilon\). \(\Sigma^{*}\) is the set of all words. A language is a set \(L \subseteq \Sigma^{*}\). For languages \(L_1, L_2\):
In this chapter \(\Sigma\) is usually the 256 byte values; examples use \(\Sigma = \{a, b\}\).
Definition 1.1.2 (Regular expressions)
The regular expressions over \(\Sigma\) and their languages are defined inductively:
Practical syntax adds abbreviations that do not add power: \(r^{+} = rr^{*}\), \(r? = r \mid \varepsilon\), a class \([abc] = a \mid b \mid c\), \([\hat{\ } S] = \Sigma \setminus S\), \(.\) = any byte except newline and carriage return, and \(r\{m,n\} = r^{m}(r?)^{n-m}\). Precedence: \(^{*}\) binds tightest, then concatenation, then \(\mid\). The size \(\lvert r \rvert\) is the number of nodes of its syntax tree. A language is regular if it is \(L(r)\) for some regular expression \(r\).
The running example
\(L(r_0) = L((a \mid b)^{*}abb) = \{abb, aabb, babb, aaabb, \dots\}\): every word over \(\{a,b\}\) whose last three symbols are \(abb\). Its syntax tree \((((a \mid b)^{*} a) b) b\) has five leaves (\(a, b, a, b, b\)), one \(\mid\), one \(^{*}\) and three concatenations, so \(\lvert r_0 \rvert = 10\).
Definition 1.1.3 (Deterministic finite automaton)
A DFA is \(A = (Q, \Sigma, \delta, q_0, F)\) with a finite set of states \(Q\), a transition function \(\delta : Q \times \Sigma \to Q\), a start state \(q_0 \in Q\) and final (accepting) states \(F \subseteq Q\). Extend \(\delta\) to words by \(\hat\delta(q, \varepsilon) = q\) and \(\hat\delta(q, wa) = \delta(\hat\delta(q, w), a)\). \(L(A) \triangleq \{\, w \mid \hat\delta(q_0, w) \in F \,\}\). A partial DFA allows \(\delta\) to be undefined; an undefined move rejects, which is the same as moving to a non-final dead state \(d\) with \(\delta(d, a) = d\) for all \(a\).
Definition 1.1.4 (ε-NFA, ε-closure)
An ε-NFA is \(N = (Q, \Sigma, \Delta, q_0, F)\) with \(\Delta \subseteq Q \times (\Sigma \cup \{\varepsilon\}) \times Q\). For \(S \subseteq Q\), the ε-closure \(E(S)\) is the least set containing \(S\) and closed under ε-edges: if \(p \in E(S)\) and \((p, \varepsilon, q) \in \Delta\) then \(q \in E(S)\). The move is \(\mathrm{move}(S, a) \triangleq \{\, q \mid \exists p \in S.\ (p, a, q) \in \Delta \,\}\). Extend to words: \(\hat\Delta(\varepsilon) = E(\{q_0\})\) and \(\hat\Delta(wa) = E(\mathrm{move}(\hat\Delta(w), a))\). \(L(N) \triangleq \{\, w \mid \hat\Delta(w) \cap F \neq \emptyset \,\}\). Equivalently, \(w \in L(N)\) iff some path from \(q_0\) to a final state spells \(w\) when ε-labels are erased.
ε-closure on the running example
In the Thompson NFA of \(r_0\) (§3), \(E(\{0\}) = \{0, 1, 2, 4, 7\}\): from 0 the ε-edges reach 1 and 7, and from 1 they reach 2 and 4; states 2, 4 and 7 have only symbol edges.
Regular expressions and closure properties¶
The algorithms in this family are constructions on automata; each is stated as a proposition and proved in §4. The two needed in practice are the product construction (intersection) and complementation of a complete DFA.
Algorithm 1.1.5 (Product and complement constructions)
- Input: complete DFAs \(A_i = (Q_i, \Sigma, \delta_i, q_i, F_i)\), \(i = 1, 2\).
- Output: DFAs for \(L(A_1) \cap L(A_2)\), \(L(A_1) \cup L(A_2)\), \(L(A_1) \setminus L(A_2)\) and \(\Sigma^{*} \setminus L(A_1)\).
- Precondition: both DFAs complete (use a dead state) over the same \(\Sigma\).
- Postcondition: the languages above (Proposition 1.1.15).
- Invariant: the product state reached on \(w\) is \((\hat\delta_1(q_1, w), \hat\delta_2(q_2, w))\).
function Product(A1, A2, accept): # accept: a Boolean function of two flags
Q ← Q1 × Q2; start ← (q1, q2)
for (p, q) in Q, a in Σ:
δ((p, q), a) ← (δ1(p, a), δ2(q, a))
F ← { (p, q) | accept(p ∈ F1, q ∈ F2) }
return (Q, Σ, δ, start, F)
# ∩: accept(x, y) = x ∧ y ∪: x ∨ y ∖: x ∧ ¬y
function Complement(A1):
return (Q1, Σ, δ1, q1, Q1 ∖ F1)
Complement needs a complete DFA
Swapping final and non-final states of a partial DFA or of an NFA does not complement the language: a word that falls off the automaton is rejected by both. Add the dead state first. RE2 and Go have no complement operator for exactly this reason: they never build the whole DFA.
Regular or not: RE2 refuses backreferences, Python's backtracking engine accepts them
Reproduce (Python 3.11.15, google-re2 1.1.20251105 from PyPI; any OS):
python3 -m venv venv && ./venv/bin/pip install -q google-re2
cat > re2demo.py <<'EOF'
import re, re2
print("python re:", re.fullmatch(r"(a+)b\1", "aabaa") is not None)
try:
re2.compile(r"(a+)b\1")
except Exception as e:
print("re2:", type(e).__name__, e)
EOF
./venv/bin/python re2demo.py 2>/dev/null
Output (complete):
What to notice: (a+)b\1 denotes \(\{a^n b a^n \mid n \ge 1\}\), which the pumping lemma (Lemma 1.1.16) shows is not regular. An engine that promises linear time (RE2) must reject it; Python's re accepts it because it is a backtracking engine (Lesson 1.2), not an automaton. "Regex" in a programming language and "regular expression" in Definition 1.1.2 are different things.
Thompson's construction¶
Algorithm 1.1.6 (McNaughton–Yamada–Thompson construction)
- Input: a regular expression \(r\) (syntax tree, Definition 1.1.2, with \(^{+}\) and \(?\) allowed).
- Output: an ε-NFA \(N(r)\) with one start state \(s\) and one final state \(f\).
- Precondition: none.
- Postcondition: \(L(N(r)) = L(r)\); \(s\) has no incoming edge; \(f\) has no outgoing edge; every state has at most two outgoing edges, and a state with a symbol edge has exactly one; \(\lvert Q \rvert \le 2 \lvert r \rvert\) (Lemma 1.1.9, Proposition 1.1.18).
- Invariant: each recursive call returns a fragment \((s, f)\) satisfying the postcondition for its sub-expression (Lemma 1.1.9).
States are numbered in creation order; Build receives an optional state given that the caller wants reused as the fragment's start (concatenation merges the left accept state with the right start state, as in the Dragon book's Fig. 3.34).
function Build(r, given): # returns (s, f)
s ← given if given ≠ none else NewState()
case r of
a (a symbol) or a class S: f ← NewState(); AddEdge(s, S, f)
ε: f ← NewState(); AddEdge(s, ε, f)
∅: f ← NewState() # no edge
r1 r2: (s, f1) ← Build(r1, given) # s comes from r1
(_, f) ← Build(r2, f1) # merge f1 with r2's start
r1 | r2: (s1, f1) ← Build(r1, none); (s2, f2) ← Build(r2, none)
f ← NewState()
AddEdge(s, ε, s1); AddEdge(s, ε, s2)
AddEdge(f1, ε, f); AddEdge(f2, ε, f)
r1*: (s1, f1) ← Build(r1, none); f ← NewState()
AddEdge(s, ε, s1); AddEdge(s, ε, f)
AddEdge(f1, ε, s1); AddEdge(f1, ε, f)
r1+: (s1, f1) ← Build(r1, none); f ← NewState()
AddEdge(s, ε, s1); AddEdge(f1, ε, s1); AddEdge(f1, ε, f)
r1?: (s1, f1) ← Build(r1, none); f ← NewState()
AddEdge(s, ε, s1); AddEdge(s, ε, f); AddEdge(f1, ε, f)
return (s, f)
function Thompson(r):
(s, f) ← Build(r, none)
return NFA with start s and final states {f}
function NewState(): allocate the next state number (0, 1, 2, …) with no edges
function AddEdge(p, label, q): append (label, q) to p's edge list
In the concatenation case the first call is made with given (so the whole fragment starts where the caller asked) and s is the start it returns; the s ← NewState() line at the top is skipped for concatenation.
The lab stores the same automaton as a program in the style of Pike and Cox [Cox09]: Char S consumes one byte of \(S\), Split x, y and Jmp x are ε-edges, Match accepts. Each fragment still has one entry and one exit, so the construction is the same; only the layout differs (solutions/labs/ch01-regex/src/Program.cpp).
Thompson's construction in Go's regexp
Reproduce (Go 1.24.7; any OS):
mkdir thompson && cd thompson
cat > main.go <<'EOF'
package main
import (
"fmt"
"regexp/syntax"
)
func main() {
re, err := syntax.Parse("(?:a|b)*abb", syntax.Perl)
if err != nil {
panic(err)
}
prog, err := syntax.Compile(re.Simplify())
if err != nil {
panic(err)
}
fmt.Print(prog)
}
EOF
printf 'module thompson\n\ngo 1.24\n' > go.mod
go run .
Output (complete):
What to notice: this is \(r_0\) compiled by Go's Thompson compiler (src/regexp/syntax/compile.go). The start is instruction 2 (marked *). alt -> 1, 3 is the star's ε-split: loop through the class [ab] (Go's simplifier merged a|b into one rune "ab" instruction, the same merge the lab's derivative engine does), or leave to a b b. Fragments with one entry and one exit, ε-edges as alt, symbol edges as rune: Algorithm 1.1.6 in an instruction list.
The position automaton¶
Definition 1.1.7 (Positions, Null, First, Last, Follow)
Linearize \(r\) by numbering its symbol (or class) leaves \(1, \dots, m\) from left to right; write \(\bar r\) for the result and \(\ell(p)\) for the symbol set at position \(p\). For a sub-expression \(s\) of \(\bar r\) define \(\mathrm{Null}(s) \iff \varepsilon \in L(s)\) and
where words of \(L(\bar r)\) are sequences of positions. The position automaton \(G(r) = (\{0, 1, \dots, m\}, \Sigma, \Delta, 0, F)\) has \((0, a, q) \in \Delta\) iff \(q \in \mathrm{First}(\bar r)\) and \(a \in \ell(q)\), \((p, a, q) \in \Delta\) iff \(q \in \mathrm{Follow}(p)\) and \(a \in \ell(q)\), and \(F = \mathrm{Last}(\bar r) \cup (\{0\}\) if \(\mathrm{Null}(\bar r))\).
Algorithm 1.1.8 (Glushkov / McNaughton–Yamada position automaton)
- Input: a regular expression \(r\) with \(m\) symbol positions.
- Output: the ε-free NFA \(G(r)\) of Definition 1.1.7.
- Precondition: none.
- Postcondition: \(L(G(r)) = L(r)\) (Theorem 1.1.12); \(G(r)\) has \(m + 1\) states.
- Invariant: after
Info(s)returns,Followis correct for every pair of positions both inside \(s\) (Lemma 1.1.11).
function Info(s): # returns (null, first, last); updates Follow
case s of
position p: return (false, {p}, {p})
ε: return (true, {}, {})
∅: return (false, {}, {})
s1 | s2: (n1, F1, L1) ← Info(s1); (n2, F2, L2) ← Info(s2)
return (n1 ∨ n2, F1 ∪ F2, L1 ∪ L2)
s1 s2: (n1, F1, L1) ← Info(s1); (n2, F2, L2) ← Info(s2)
for p in L1: Follow[p] ← Follow[p] ∪ F2
return (n1 ∧ n2, F1 ∪ (F2 if n1 else {}), L2 ∪ (L1 if n2 else {}))
s1*, s1+: (n, F1, L1) ← Info(s1)
for p in L1: Follow[p] ← Follow[p] ∪ F1
return (true if s = s1* else n, F1, L1)
s1?: (n, F1, L1) ← Info(s1); return (true, F1, L1)
function PositionAutomaton(r):
number the leaves of r 1..m; Follow[p] ← {} for all p
(null, first, last) ← Info(r)
edges from 0: to every q in first, labelled ℓ(q)
edges from p ≥ 1: to every q in Follow[p], labelled ℓ(q)
final ← last ∪ ({0} if null else {})
The position construction inside GNU grep
Reproduce (gnulib lib/dfa.c at tag v1.0, the DFA matcher of GNU grep 3.11 and gawk; any OS with curl):
curl -sSfL https://raw.githubusercontent.com/coreutils/gnulib/v1.0/lib/dfa.c -o dfa.c
sed -n '2640,2649p' dfa.c
grep -n '^dfaanalyze\|^build_state' dfa.c
Output (complete):
Firstpos: The firstpos of a node is the set of positions (nonempty leaves)
that could correspond to the first character of a string matching the
regexp rooted at the given node.
* EMPTY leaves have empty firstpos.
* The firstpos of a nonempty leaf is that leaf itself.
* The firstpos of a QMARK, STAR, or PLUS node is the firstpos of its
argument.
* The firstpos of a CAT node is the firstpos of the left argument, union
the firstpos of the right if the left argument is nullable.
* The firstpos of an OR node is the union of firstpos of each argument.
2694:dfaanalyze (struct dfa *d, bool searchflag)
3009:build_state (state_num s, struct dfa *d, unsigned char uc)
What to notice: GNU grep does not build a Thompson NFA at all. dfaanalyze computes nullable/firstpos/lastpos/follows exactly as Info does (the comment is the CAT case of Algorithm 1.1.8), and build_state then builds DFA states, as sets of positions, on demand (Lesson 1.2's lazy DFA).
3. Worked example¶
Thompson's construction¶
Thompson's construction on \(r_0 = (a \mid b)^{*}abb\). The table lists the fragments in the order Build finishes them (innermost first). It was generated with the course oracle (tools/course/lib/regex.py, thompson(..., trace)) and is the NFA of Dragon Fig. 3.34.
| sub-expression | rule | start | accept | note |
|---|---|---|---|---|
a |
symbol | 2 | 3 | |
b |
symbol | 4 | 5 | |
a\|b |
alternation | 1 | 6 | new states 1 (before the leaves) and 6 (after) |
(a\|b)* |
star | 0 | 7 | 0 was created first: star's start precedes its body |
(a\|b)*a |
concatenation | 0 | 8 | merges 7 with the start of a |
(a\|b)*ab |
concatenation | 0 | 9 | merges 8 |
(a\|b)*abb |
concatenation | 0 | 10 | merges 9 |
flowchart LR
s0([0]) -->|ε| s1((1))
s0 -->|ε| s7((7))
s1 -->|ε| s2((2))
s1 -->|ε| s4((4))
s2 -->|a| s3((3))
s4 -->|b| s5((5))
s3 -->|ε| s6((6))
s5 -->|ε| s6
s6 -->|ε| s1
s6 -->|ε| s7
s7 -->|a| s8((8))
s8 -->|b| s9((9))
s9 -->|b| s10(((10)))Eleven states for \(\lvert r_0 \rvert = 9\) nodes; every state has at most two out-edges; 0 has no incoming edge; 10 (accepting) has no outgoing edge. The postcondition of Algorithm 1.1.6 holds.
ε-closure of \(\{0\}\) by the stack algorithm (pop a state, push its ε-successors not yet in the set), from eps_closure(..., trace):
| pop | ε-successors added | stack after | closure so far |
|---|---|---|---|
| (init) | – | 0 | {0} |
| 0 | {1, 7} | 1 7 | {0, 1, 7} |
| 7 | – | 1 | {0, 1, 7} |
| 1 | {2, 4} | 2 4 | {0, 1, 2, 4, 7} |
| 4 | – | 2 | {0, 1, 2, 4, 7} |
| 2 | – | (empty) | {0, 1, 2, 4, 7} |
The position automaton¶
The position automaton of \(r_0\). Linearize: \(\bar r_0 = (a_1 \mid b_2)^{*} a_3 b_4 b_5\). Info returns, bottom-up:
| sub-expression | Null | First | Last | Follow updates |
|---|---|---|---|---|
| \(a_1 \mid b_2\) | no | {1, 2} | {1, 2} | – |
| \((a_1 \mid b_2)^{*}\) | yes | {1, 2} | {1, 2} | Follow(1), Follow(2) ∪= |
| \((\dots)^{*} a_3\) | no | {1, 2, 3} | {3} | Follow(1), Follow(2) ∪= |
| \((\dots) a_3 b_4\) | no | {1, 2, 3} | {4} | Follow(3) ∪= |
| \((\dots) a_3 b_4 b_5\) | no | {1, 2, 3} | {5} | Follow(4) ∪= |
So Follow(1) = Follow(2) = {1, 2, 3}, Follow(3) = {4}, Follow(4) = {5}, Follow(5) = {}. The automaton has 6 states and no ε-edges:
| state | on a | on b | final |
|---|---|---|---|
| → 0 | {1, 3} | {2} | |
| 1 (\(a_1\)) | {1, 3} | {2} | |
| 2 (\(b_2\)) | {1, 3} | {2} | |
| 3 (\(a_3\)) | {} | {4} | |
| 4 (\(b_4\)) | {} | {5} | |
| 5 (\(b_5\)) | {} | {} | yes |
States 0, 1 and 2 have identical rows: the position automaton is small but not minimal. Lesson 1.4 merges such states.
Regular expressions and closure properties¶
"An identifier that is not the keyword if" is a difference of two regular languages, \(L_1 = L([a\text{-}z]^{+})\) minus \(L_2 = \{\mathtt{if}\}\). Take the alphabet \(\{i, f, x\}\), where \(x\) stands for every other letter. Complete DFAs: \(A_1\) has states \(P_0\) (start) and \(P_1\) (final, loops on every letter); \(A_2\) has \(Q_0 \xrightarrow{i} Q_1 \xrightarrow{f} Q_2\) (final), every other move going to the dead state \(Q_d\). Algorithm 1.1.5 with \(\mathit{accept}(x, y) = x \land \lnot y\), exploring only reachable pairs:
| step | product state | on i | on f | on x | final? (\(P \in F_1 \land Q \notin F_2\)) |
|---|---|---|---|---|---|
| 1 | → \((P_0, Q_0)\) | \((P_1, Q_1)\) new | \((P_1, Q_d)\) new | \((P_1, Q_d)\) | no (\(P_0 \notin F_1\)) |
| 2 | \((P_1, Q_1)\) | \((P_1, Q_d)\) | \((P_1, Q_2)\) new | \((P_1, Q_d)\) | yes |
| 3 | \((P_1, Q_d)\) | \((P_1, Q_d)\) | \((P_1, Q_d)\) | \((P_1, Q_d)\) | yes |
| 4 | \((P_1, Q_2)\) | \((P_1, Q_d)\) | \((P_1, Q_d)\) | \((P_1, Q_d)\) | no (\(Q_2 \in F_2\)) |
Four reachable states out of \(2 \times 4 = 8\). The word i ends in \((P_1, Q_1)\) (accepted: an identifier), if in \((P_1, Q_2)\) (rejected: the keyword), iff in \((P_1, Q_d)\) (accepted). A lexer generator gets the same effect more cheaply with rule priority (Lesson 1.6).
Try it
./course drill epsilon-closure --seed 5 --difficulty hard: build the Thompson NFA of b+b(a|b)? yourself, then check every closure with --solution.
4. Invariants and correctness¶
Thompson's construction¶
Lemma 1.1.9 (Fragment invariant)
For every sub-expression \(s\), Build(s, given) returns \((s_0, f)\) such that (i) \(f\) is a state created by this call and has no outgoing edges when the call returns; (ii) no edge created by this call enters \(s_0\); (iii) every path from \(s_0\) to \(f\) uses only states created by this call (plus \(s_0\) if it was given); (iv) the call creates at most \(2\lvert s \rvert\) states and every created state has at most two outgoing edges, exactly one if it has a symbol edge.
Proof
By structural induction on \(s\). Base (symbol, class, ε, ∅): the call creates \(f\) (and \(s_0\) unless given), adds at most one edge \(s_0 \to f\); (i)–(iv) are immediate with \(2 \le 2 \cdot 1\) states. Concatenation \(s_1 s_2\): by induction \(f_1\) has no out-edges after the first call; the second call is given \(f_1\) as its start and, by (ii) for \(s_2\), adds no edge into it, but it adds \(f_1\)'s out-edges, which is allowed because \(f_1\) is no longer a fragment exit. \(f = f_2\) satisfies (i) by induction. Edges into \(s_0\) could only come from the second call, whose states are fresh or \(f_1 \neq s_0\), so (ii) holds. Paths from \(s_0\) to \(f_2\) must cross \(f_1\) (the only state shared by the two fragments), giving (iii). State count \(\le 2\lvert s_1\rvert + 2\lvert s_2\rvert - 1 + 0 \le 2 \lvert s \rvert\). Alternation, star, plus, option: the new start \(s_0\) receives no edge (the loop edge of \(^{*}\) and \(^{+}\) goes to \(s_1\), not \(s_0\)); the new \(f\) gets only incoming edges; the sub-fragments' exits get one or two ε-edges; two new states are added, so the count is \(\le 2\lvert s_1 \rvert (+ 2 \lvert s_2 \rvert) + 2 \le 2 \lvert s \rvert\). Out-degree: \(s_0\) gets two ε-edges; \(f_1\) gets at most two. \(\square\)
Theorem 1.1.10 (Correctness of Thompson's construction)
For every regular expression \(r\), \(L(N(r)) = L(r)\).
Proof
We show by structural induction on \(s\) that for the fragment \((s_0, f)\) of \(s\), the words spelled by paths from \(s_0\) to \(f\) (ε erased) are exactly \(L(s)\). By Lemma 1.1.9 (iii) such paths stay inside the fragment, so edges added later elsewhere do not create new paths; by (ii) they never return to \(s_0\).
Base: one edge labelled \(a\) (or a class), ε, or no edge: the words are \(\{a\}\), \(\{\varepsilon\}\), \(\emptyset\).
Alternation: a path leaves \(s_0\) through \(s_1\) or \(s_2\). The two sub-fragments share no state and no edge connects them, so the path stays in one of them until it takes \(f_1 \to f\) or \(f_2 \to f\). The words are \(L(s_1) \cup L(s_2)\) by induction.
Concatenation (with merging): the two fragments share exactly one state, \(f_1\), which is the first fragment's exit and the second fragment's start. Edges of the first call join first-fragment states; edges of the second call join second-fragment states; none enters \(f_1\) (Lemma 1.1.9 (ii) for \(s_2\)). A path from \(s_0\) to \(f_2\) must therefore reach \(f_1\) inside the first fragment (where \(f_1\) has no out-edges, so it appears there only at the end), and after leaving \(f_1\) it can never come back. It splits uniquely into a path \(s_0 \leadsto f_1\) of the first fragment and a path \(f_1 \leadsto f_2\) of the second. By induction the words are \(L(s_1)\,L(s_2)\), and any two such paths compose.
Star: a path \(s_0 \leadsto f\) either takes \(s_0 \to f\) (word ε) or enters \(s_1\), runs \(k \ge 1\) times through the body from \(s_1\) to \(f_1\), taking the loop edge \(f_1 \to s_1\) between runs, and exits by \(f_1 \to f\); each run spells a word of \(L(s_1)\) by induction. So the words are \(\bigcup_{k\ge0} L(s_1)^k = L(s_1)^{*}\). Plus and option are the same argument without the bypass edge (\(k \ge 1\)) and without the loop edge (\(k \le 1\)) respectively.
Applying the claim to the whole expression and Definition 1.1.4 gives \(L(N(r)) = L(r)\). \(\square\)
When it breaks: backreferences ((a+)b\1) cannot be compiled by any such local construction because the language is not regular (Lemma 1.1.16). Lookahead and anchors need extra machinery (RE2 handles ^ and \b with "empty-width" instructions); lazy quantifiers change which match is reported but not the language.
The position automaton¶
Lemma 1.1.11 (Local characterization)
Let \(\bar r\) be linearized. A nonempty sequence of positions \(p_1 \cdots p_k\) is in \(L(\bar r)\) iff \(p_1 \in \mathrm{First}(\bar r)\), \(p_{i+1} \in \mathrm{Follow}(p_i)\) for \(1 \le i < k\), and \(p_k \in \mathrm{Last}(\bar r)\). Moreover Info computes Null, First, Last and Follow exactly.
Proof sketch (full proof: [BS86, §2]; also [Dragon2 §3.9.5])
Exactness of Info is by structural induction, one case per rule: e.g. for \(s_1 s_2\), a word of \(L(s_1 s_2)\) starts with a position of \(s_1\) unless the \(s_1\) part is empty, which is possible iff \(\mathrm{Null}(s_1)\); two adjacent positions \(p, q\) in a word of \(L(s_1 s_2)\) are either both in \(s_1\), both in \(s_2\) (handled by induction), or \(p\) ends the \(s_1\) part and \(q\) starts the \(s_2\) part, which is exactly \(\mathrm{Last}(s_1) \times \mathrm{First}(s_2)\). The star case adds \(\mathrm{Last}(s_1) \times \mathrm{First}(s_1)\) for consecutive iterations. The characterization holds because in a linearized expression each position occurs once, so membership depends only on the first position, the last position and adjacent pairs: a regular expression whose symbols are all distinct denotes a local language. The proof of the "if" direction builds the parse of the sequence by induction on \(\bar r\) from the adjacency facts; [BS86] gives it in full.
Theorem 1.1.12 (Correctness of the position automaton)
\(L(G(r)) = L(r)\), and \(G(r)\) has exactly \(m + 1\) states and no ε-edges.
Proof
A run of \(G(r)\) on \(w = a_1 \cdots a_k\) (\(k \ge 1\)) is a state sequence \(0, p_1, \dots, p_k\) with \(p_1 \in \mathrm{First}\), \(p_{i+1} \in \mathrm{Follow}(p_i)\), \(a_i \in \ell(p_i)\) (Definition 1.1.7), accepting iff \(p_k \in \mathrm{Last}\). By Lemma 1.1.11 such runs correspond one-to-one to position sequences in \(L(\bar r)\) whose \(i\)-th position can read \(a_i\); erasing the numbering maps \(L(\bar r)\) onto \(L(r)\), so \(w \in L(r)\) iff an accepting run exists. For \(k = 0\), \(0 \in F\) iff \(\mathrm{Null}(\bar r)\) iff \(\varepsilon \in L(r)\). The state count is by construction. \(\square\)
Regular expressions and closure properties¶
Theorem 1.1.13 (Kleene)
A language is regular (denoted by a regular expression) if and only if some finite automaton (DFA or ε-NFA) recognizes it.
Proof sketch (full proof: [HMU07 §3.2]; original: [Kle56])
(⇒) Theorem 1.1.10 gives an ε-NFA; the subset construction (Lesson 1.2, Theorem 1.2.10) turns it into a DFA. (⇐) Number the states \(1..n\) and let \(R^{(k)}_{ij}\) be the words that take the automaton from \(i\) to \(j\) with all intermediate states numbered \(\le k\). Then \(R^{(0)}_{ij}\) is a finite set of symbols (plus ε if \(i = j\)), hence regular, and \(R^{(k)}_{ij} = R^{(k-1)}_{ij} \cup R^{(k-1)}_{ik}\,(R^{(k-1)}_{kk})^{*}\,R^{(k-1)}_{kj}\) (a path either avoids \(k\) or splits at its visits to \(k\)). By induction on \(k\) every \(R^{(k)}_{ij}\) is regular, and \(L = \bigcup_{j \in F} R^{(n)}_{q_0 j}\).
Lemma 1.1.14 (Product invariant)
In the product of Algorithm 1.1.5, \(\hat\delta((q_1, q_2), w) = (\hat\delta_1(q_1, w), \hat\delta_2(q_2, w))\) for every word \(w\).
Proof
By induction on \(\lvert w \rvert\): true for ε by the choice of start state; if true for \(w\), then \(\hat\delta((q_1,q_2), wa) = \delta((\hat\delta_1(q_1,w), \hat\delta_2(q_2,w)), a) = (\delta_1(\hat\delta_1(q_1,w),a), \delta_2(\hat\delta_2(q_2,w),a))\) by the definition of \(\delta\). \(\square\)
Proposition 1.1.15 (Closure properties)
Regular languages are closed under union, concatenation, star, intersection, complement, difference and reversal.
Proof
Union, concatenation and star: by Definition 1.1.2. Intersection, union and difference: by Lemma 1.1.14, \(w\) is accepted by the product iff accept\((\hat\delta_1(q_1, w) \in F_1, \hat\delta_2(q_2, w) \in F_2)\), i.e. iff \(w \in L_1 \cap L_2\) (resp. ∪, ∖). Complement: in a complete DFA \(\hat\delta(q_0, w)\) is defined for every \(w\), so \(w \notin L(A)\) iff \(\hat\delta(q_0, w) \in Q \setminus F\). Reversal: reverse every edge of an ε-NFA, make the old final states start states (via a fresh start with ε-edges) and the old start the final state; a path spelling \(w\) becomes one spelling \(w^{R}\). \(\square\)
Lemma 1.1.16 (Pumping lemma)
If \(L\) is regular, there is \(n \ge 1\) such that every \(z \in L\) with \(\lvert z \rvert \ge n\) can be written \(z = uvw\) with \(\lvert uv \rvert \le n\), \(\lvert v \rvert \ge 1\) and \(u v^{i} w \in L\) for all \(i \ge 0\).
Proof
Let \(A\) be a DFA for \(L\) with \(n\) states. The run on \(z\) visits \(\lvert z \rvert + 1 > n\) states; among the first \(n + 1\) of them some state repeats (pigeonhole): \(\hat\delta(q_0, u) = \hat\delta(q_0, uv)\) with \(\lvert uv \rvert \le n\), \(\lvert v \rvert \ge 1\). The loop spelling \(v\) can be taken any number \(i\) of times, and the run still ends in the same final state after \(w\). \(\square\)
Corollary 1.1.17 (Nested comments are not regular)
Let \(C\) be the set of well-nested Pebble block comments over the alphabet \(\{\mathtt{/*}, \mathtt{*/}, x\}\) (treat each two-byte delimiter as one symbol). \(C\) is not regular; neither is the byte-level language.
Proof
Suppose \(C\) regular. Then \(C \cap L(\mathtt{/*}^{*}\,\mathtt{*/}^{*}) = \{\mathtt{/*}^{k}\,\mathtt{*/}^{k} \mid k \ge 1\}\) is regular (Proposition 1.1.15). Take \(n\) from Lemma 1.1.16 and \(z = \mathtt{/*}^{n}\,\mathtt{*/}^{n}\). Since \(\lvert uv \rvert \le n\), \(v\) consists of opening delimiters only, so \(u v^{2} w\) has more openers than closers and is not in the language: contradiction. For the byte-level language \(C_{\mathrm{bytes}}\), let \(h\) map \(\mathtt{/*} \mapsto\) the bytes /*, \(\mathtt{*/} \mapsto\) */ and \(x \mapsto\) x. \(h\) is a homomorphism and \(C = h^{-1}(C_{\mathrm{bytes}}) \cap \{\mathtt{/*}, \mathtt{*/}, x\}^{*}\); regular languages are closed under inverse homomorphisms [HMU07 §4.2.4], so \(C_{\mathrm{bytes}}\) regular would make \(C\) regular. \(\square\)
This is why the Pebble lexer counts nesting depth (solutions/pebble/lib/Lex/src/Lexer.cpp, skipBlockComment) and why the table-driven lexer of the lab (inputs/pebble.lexspec) only recognizes non-nested comments.
5. Complexity¶
Let \(n = \lvert r \rvert\) (syntax-tree nodes) and \(m\) = number of symbol positions (\(m \le n\)).
| Technique | Time | States | Edges | Variables |
|---|---|---|---|---|
| Thompson (Algorithm 1.1.6) | \(\Theta(n)\) | \(\le 2n\) | \(\le 4n\) (≤ 2 per state) | \(n = \lvert r \rvert\) |
| Position automaton (Algorithm 1.1.8) | \(O(n + m^{2})\) with sets as bit vectors | \(m + 1\) | \(O(m^{2})\), tight | \(m\) positions |
| Product (Algorithm 1.1.5) | \(O(\lvert Q_1 \rvert \lvert Q_2 \rvert \lvert\Sigma\rvert)\) | \(\lvert Q_1 \rvert \lvert Q_2 \rvert\) | same | DFA sizes |
Proposition 1.1.18 (Size of the Thompson NFA)
\(N(r)\) has at most \(2\lvert r \rvert\) states and \(4 \lvert r \rvert\) edges, and is built in \(\Theta(\lvert r \rvert)\) time.
Proof
States: Lemma 1.1.9 (iv). Edges: each state has at most two out-edges. Time: Build is called once per syntax-tree node and does \(O(1)\) work besides its recursive calls (each AddEdge is an append). \(\square\)
Proposition 1.1.19 (The position automaton can have quadratically many edges)
For \(r_m = (a_1 \mid a_2 \mid \cdots \mid a_m)^{*}\) over \(m\) distinct symbols, \(G(r_m)\) has \(m + 1\) states and \(m^{2} + m\) edges, while \(N(r_m)\) has \(O(m)\) edges.
Proof
Every position is in \(\mathrm{First}\) and in \(\mathrm{Last}\) of the body, and the star rule adds \(\mathrm{Last} \times \mathrm{First}\) to Follow: every position follows every position, giving \(m^{2}\) edges between positions plus \(m\) edges from state 0. \(\lvert r_m \rvert = 2m\) nodes (\(m\) leaves, \(m - 1\) alternations, one star), so Proposition 1.1.18 bounds the Thompson NFA by \(8m\) edges. \(\square\)
Pathological input. Counted repetition is desugared: x{1000} is 1000 copies of x, so a short pattern can have a huge \(\lvert r \rvert\). Nesting multiplies: ((x{100}){100}){100} has \(10^{6}\) leaves. Go's parser rejects repetition counts above 1000 (syntax.ErrInvalidRepeatSize), RE2 caps program size through its memory budget, and the lab caps each bound at 100 (SPEC.md, R1).
At scale. The lab's ch01-regexbench compiles each benchmark pattern (Thompson, subset construction and Hopcroft together) in well under a millisecond; for lexers the NFA is a one-time build cost (135 table states for all of Pebble, built in 2.6 ms on the course container; Lesson 1.5 §8).
6. Variants and refinements¶
Regular expressions and closure properties¶
- Extended regular expressions with \(\cap\) and complement ([ORT09]; re2c supports difference of character classes,
[a-z] \ [aeiou]): same power, exponentially more succinct; complement forces a complete DFA, which is why RE2 and Go omit it. - POSIX vs Perl semantics differ in which match or submatch is reported (leftmost-longest vs leftmost-first), not in which strings match. Lexers want longest (Lesson 1.6).
- Backreferences and lookaround leave the regular languages; matching with backreferences is NP-hard in general, which is why they come with backtracking engines.
Thompson's construction¶
- Instruction-list form (Pike, Cox [Cox09]): the same fragments as
Char/Split/Jmp/Match; trades a graph for a compact array that a VM can run. Used by RE2, Go and the lab. - ε-concatenation instead of merging [HMU07 §2.5]: an ε-edge from \(f_1\) to \(s_2\) instead of merging; one extra edge per concatenation, simpler invariants.
- UTF-8 automata (RE2, Rust
regex-automata): a Unicode class compiles to a small byte-level automaton so the engine can stay byte-based; the cost is more states per class.
The position automaton¶
- Berry–Sethi [BS86] derive the position automaton from derivatives and build it in \(O(m^{2})\); Brüggemann-Klein's star normal form removes redundant Follow computations to reach time linear in the output.
- Direct DFA construction (Dragon §3.9 "followpos", GNU grep): run the subset construction on position sets without ever materializing the NFA.
- Antimirov's partial-derivative automaton (Lesson 1.3) is a quotient of the position automaton: never larger, often smaller.
7. In real compilers¶
Regular expressions and closure properties¶
Where regular languages show up
Language standards specify tokens with regular-expression grammars (C: "Lexical elements", Python: "Lexical analysis"), even when the compiler's lexer is hand-written. Lexer generators take them literally: flex [FLEX-Manual] and re2c [RE2C-Manual] compile rule lists to DFAs. RE2 [RE2-DFA] restricts itself to regular constructs to guarantee linear time; LLVM's own regex library (llvm/lib/Support/regexec.c, used by FileCheck) supports POSIX backreferences and falls back to backtracking only when a pattern uses them.
The real-world box for this technique is under §2 ("RE2 refuses backreferences").
Thompson's construction¶
- Go
src/regexp/syntax/compile.go—compiler.compileemits oneInstfragment per operator (Go 1.24.7) [GO-Regexp]; box in §2. - RE2
re2/compile.cc—Compiler::Compile, the same scheme with byte-range instructions for UTF-8 [RE2-DFA]. - LLVM
llvm/lib/Support/regcomp.c—llvm_regcompcompiles POSIX regexes (Henry Spencer's library) into a strip of opcodes thatregengine.incsimulates as sets of states [LLVM-Regex].
Find where LLVM does it. Open llvm/lib/Support/regexec.c at llvmorg-23.1.2 and find how llvm_regexec chooses between smatcher and lmatcher. Question: what property of the compiled pattern decides it, and what data structure represents a set of NFA states in the small matcher? (Quiz llvm-regex-state-sets.)
The position automaton¶
- GNU grep / gawk — gnulib
lib/dfa.c:dfaanalyzecomputes nullable/firstpos/lastpos/follows, andbuild_statebuilds DFA states lazily from position sets [GNULIB-DFA]; box in §2. - Hyperscan (Intel's multi-pattern matcher) builds a Glushkov NFA as its central graph representation; we cite it without a pinned source pointer because we did not verify a path at a fixed tag.
8. Comparison¶
| Technique | Power / precision | Speed | Output / error quality | Implementation effort | Typical use |
|---|---|---|---|---|---|
| Regular expressions (+ closure constructions) | exactly the regular languages; no nesting, no counting | product: \(O(\lvert Q_1\rvert\lvert Q_2\rvert\lvert\Sigma\rvert)\) | declarative; errors are "no match" | a parser for the syntax | specifying tokens; RE2/Go/grep patterns |
| Thompson (MYT) | any regex → ε-NFA | \(\Theta(\lvert r\rvert)\) build; ≤ \(2\lvert r\rvert\) states | keeps the regex's structure (good for submatches) | small (one case per operator) | front end of NFA simulators, lazy DFAs, lexer generators |
| Position (Glushkov) | any regex → ε-free NFA with \(m+1\) states | \(O(m^{2})\) build and edges | states = symbol occurrences (easy to relate to the pattern) | moderate (Null/First/Last/Follow) | direct DFA construction (grep, Dragon §3.9), bit-parallel matchers |
Choose Thompson when you will simulate the NFA or build DFA states lazily, and you want construction linear in the pattern. Choose the position automaton when you want no ε-edges (bit-parallel simulation, direct subset construction over positions) and the pattern has few alternatives under stars. Use the closure constructions when a specification combines languages (keywords minus identifiers, complement of a delimiter), and always on complete DFAs.
9. Assessment¶
| Technique | Quiz ids (solutions/quizzes/ch01.yaml) |
Drill | Flashcard tag | Exercises |
|---|---|---|---|---|
| Regular expressions and closure properties | nested-comments-not-regular, closure-complement, llvm-regex-state-sets |
justification below | regular-languages |
— |
| Thompson's construction | thompson-state-count, thompson-closure |
./course drill epsilon-closure (hard builds the NFA) |
thompson |
Lab L1–L2 |
| Position automaton | glushkov-follow, thompson-state-count |
./course drill epsilon-closure --difficulty medium (compare with the ε-free form in --solution) |
glushkov |
— |
No drill generates closure-property problems: they are proofs, not computations, and the quiz asks for the proof steps (nested-comments-not-regular) and their preconditions (closure-complement).
Pitfall
"Regex" features in programming languages (backreferences, lookaround, possessive quantifiers) are not regular expressions. A lexer that needs them is no longer a finite automaton, and linear-time guarantees disappear.
References¶
See the chapter references.