THE FOLD / BOSS / THE FIREWALL / THE THOMPSON NFA
THE THOMPSON NFA
regex to NFA — match by advancing a whole state set, no backtracking
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Thompson’s construction turns any regular expression into a nondeterministic finite automaton (NFA) with a handful of gadgets — one for a literal, one for concatenation, one for alternation (|), one for star (*) — glued by ε-transitions. To match a string, you simulate the NFA by tracking the set of states currently reachable, stepping the whole set per character.
This runs in O(nm) with no catastrophic backtracking — the guarantee grep and RE2 give and naive backtracking engines lack.
LIT verified live: for several patterns over {a,b}, the NFA set-simulation’s accept/reject matches a reference regex engine across all strings up to length 6 (window.__thompsonnfa). FIG no framing; exact automaton simulation.
This runs in O(nm) with no catastrophic backtracking — the guarantee grep and RE2 give and naive backtracking engines lack.
LIT verified live: for several patterns over {a,b}, the NFA set-simulation’s accept/reject matches a reference regex engine across all strings up to length 6 (window.__thompsonnfa). FIG no framing; exact automaton simulation.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-firewall — the pattern-matching guard that inspects every passing string. Thompson’s NFA is the firewall’s engine: match by rule, in guaranteed linear time. AVAN (AI) built the instrument: the regex parser, the set-of-states simulation, the exhaustive check against a reference engine.
Credit as content: Ken Thompson (1968, Regular Expression Search Algorithm — the basis of grep). The weave: David names the firewall; I compile a regex into an NFA, simulate it by advancing a whole set of states at once, and confirm it accepts exactly the right strings.
Credit as content: Ken Thompson (1968, Regular Expression Search Algorithm — the basis of grep). The weave: David names the firewall; I compile a regex into an NFA, simulate it by advancing a whole set of states at once, and confirm it accepts exactly the right strings.
3 ONE DIMENSION
The four Thompson gadgets: a literal edge, concatenation (glue end to start), alternation (an ε-fork into two branches), and star (an ε-loop). Any regex is built by nesting these.
4 TWO DIMENSIONS · INTERACTIVE
Choose a regex over {a,b} and test strings. The NFA simulation tracks the reachable state set and reports accept/reject, checked against a reference regex over all short strings.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the reachable state set advancing across the string, one step per character.
AVAN’s addition (the inverse-companion): nondeterminism is tamed by carrying a set of states at once. Instead of guessing which path to take and backtracking when wrong, the simulation advances all possible current states in parallel — so the exponential blow-up of backtracking becomes a linear sweep over a bounded state set (the subset construction, done lazily). The inverse of ‘try each path and backtrack’ is ‘advance every path simultaneously.’ Magenta is the exponential backtracking tree a naive engine explores; green is the single set-of-states that walks the string once. Determinise on the fly and nondeterminism costs nothing — the reason a good regex engine can never be made to hang.
LIT Genuine Thompson NFA construction (Thompson 1968, the basis of grep). Verified live: compiling regexes (concat, |, *) over {a,b} into an NFA and simulating by set-of-states, the accept/reject verdict matches JavaScript's reference RegExp for all strings up to length 6 across 5 patterns (window.__thompsonnfa.matchesReference).
FIG No framing: the regex parser, the set-of-states simulation, and the exhaustive reference check run in-browser and agree exactly. The AVAN inverse is honest — carrying a set of states advances all nondeterministic paths in parallel, turning the exponential backtracking tree into a linear sweep over a bounded state set (lazy subset construction); magenta is the backtracking a naive engine explores, green the single advancing state set.
FIG No framing: the regex parser, the set-of-states simulation, and the exhaustive reference check run in-browser and agree exactly. The AVAN inverse is honest — carrying a set of states advances all nondeterministic paths in parallel, turning the exponential backtracking tree into a linear sweep over a bounded state set (lazy subset construction); magenta is the backtracking a naive engine explores, green the single advancing state set.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE FIREWALL · David Lee Wise (ROOT0), with AVAN