Thompson's Construction¶
A compositional conversion of a classical regular expression into a language-equivalent ε-NFA.
Core Idea¶
Thompson's construction recursively converts a classical regular expression into an ε-NFA accepting the same language. Literal fragments are combined by local rules for concatenation, alternation, and repetition; the fragments retain a composable entry/exit interface. A textbook variant has one explicit start and final state per fragment, while an implementation can instead keep patchable outgoing arrows until completion.[ref-838d634bf021][ref-5e2c12186f46]
Scope of Application¶
A text-search pattern may be compiled once and matched over many inputs. Compiler lexers can compile a regular expression for each token class and join the resulting machines at a new ε-branching start. NFA simulation, DFA conversion, longest-match choice, and lexer rule priority happen downstream; they do not define the construction.[ref-5e2c12186f46][ref-6de75cc80938]
Clarity¶
The necessary roles are a classical regular-expression source, composable automaton fragments, operator-local wiring rules, and an ε-NFA whose language equals the source's. Backreference syntax lies outside these rules; some fixed-choice backreference patterns still denote regular languages, while a variable-length case such as (a*)b\1 requires matching the same arbitrary count on both sides of b and is nonregular. The textbook NFA size is linear in expression length, but that does not imply matching a text of length \(m\) against a length-\(n\) expression costs \(O(m+n)\); cited NFA simulation can take \(O(mn)\).[ref-838d634bf021][ref-5e2c12186f46]
Manages Complexity¶
The fragment interface means each regex syntax-tree node can be compiled locally while preserving a global language invariant. For a(b|c)*, build symbols, branch between b and c, add the star bypass and loop, and concatenate after a. That provides a small machine without reasoning separately about every accepted string.[ref-838d634bf021][ref-6de75cc80938]
Abstract Reasoning¶
If \(L(N_R)=L(R)\) for fragments corresponding to subexpressions, correct concatenation, alternation, and star wiring preserve the matching language operation. Induction over the source expression then gives \(L(N)=L(R)\) for the completed automaton. The regex and ε-NFA differ in representation, not in the strings they denote.[^ref-838d634bf021]
Knowledge Transfer¶
The conversion transfers from a single search pattern to per-token lexer patterns. What transfers is the formal operator composition, not how the resulting machine is run or optimized. Modern ε-NFA diagrams are a formal reconstruction of Thompson's historical machine-code technique; early Unix grep should not be assumed to have used this matching algorithm.[ref-5e2c12186f46][ref-6de75cc80938]
[^ref-838d634bf021]: Alfred Aho and Rajeev Verma, Columbia COMS W3261, “Lecture 4: Regular Expressions and Finite Automata”, §2, directly checked. [^ref-5e2c12186f46]: Russ Cox, “Regular Expression Matching Can Be Simple And Fast” (2007), compiling, performance, and history sections, directly checked. [^ref-6de75cc80938]: NYU compiler lecture, “Compilers Lecture #4”, §§3.7.4 and 3.8, directly checked.
Relationships to Other Abstractions¶
Current abstraction Thompson's Construction Domain-specific
Parents (1) — more general patterns this builds on
-
Thompson's Construction presupposes Regular Expression Domain-specific
The construction recursively compiles a regular expression's literals and operators.
Condition / exception classical regular-language source
Hierarchy path (1) — routes to 1 parentless root
- Thompson's Construction → Regular Expression → Formal Language → Set and Membership
Neighborhood in Abstraction Space¶
Thompson's Construction sits in a sparse region of the domain-specific corpus (65th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Type Systems & Functional Constructs (18 abstractions)
Nearest neighbors
- String-to-String Correction Problem — 0.85
- Antihomomorphism — 0.84
- Operator (computer programming) — 0.84
- Program Transformation — 0.84
- Lexical analysis — 0.84
Computed from structural-signature embeddings · 2026-10-08