THE GLUSHKOV CONSTRUCTION number the letters; the follow relation is the automaton
To turn a regular expression into a finite automaton, number every letter position, then compute three sets: which positions can start a match (first), which can end it (last), and which can follow each other. Those sets are the automaton — one state per letter, no epsilon-transitions. The whole NFA fits in a handful of bitmasks, and a match is a few bitwise AND/OR steps.
THE TECHNIQUE first, last, follow -> a bitmask NFA
For (a|b)*abb the five letter-positions become five bits. Reading a symbol keeps the active positions whose label matches, then jumps to their follow set. Watch the active-set bitmask evolve over aabb and land on the final position — pure bitwise: live demo
HISTORY & CREDIT Glushkov 1961; McNaughton-Yamada 1960
“Regex-to-NFA means Thompson’s epsilon-transitions.” — not the only way. Thompson’s construction (dart 130) adds ε-moves; Glushkov’s makes an ε-free NFA with exactly one state per letter (plus a start) — smaller, and the standard route to a DFA. cited
1960 · McNaughton & Yamada — “Regular expressions and state graphs for automata”: the position/follow construction (often co-named). 1961 · Victor Glushkov — “The abstract theory of automata”: the same ε-free position automaton, the name that stuck in the West. 1996+ · Brüggemann-Klein, Berry & Sethi — efficient constructions and the tie to the Berry-Sethi “marked” automaton.
One state per letter is the tightest an NFA can be for a regex — and every ε-free NFA determinises without the ε-closure step, which is why Glushkov is the usual on-ramp to a DFA (dart 178’s minimiser). Glushkov 1961 / McNaughton-Yamada 1960
RECOMMEND FOR I-13 the bitmask NFA, computed
The position NFA for (a|b)*abb runs on the canonical compiler as bitmask AND/OR — the active set landing on the final position accepts:
$ i13 run glushkov.i13 # (a|b)*abb, positions 1..5 as bits; follow-sets + label masks
aabb: active 5 -> 5 -> 10 -> 18 -- bitmask of live positions after each symbol
accepted = 16 -- final position 5 (bit 16) is live -> ACCEPT
Recommend: the Glushkov construction is LIT and a natural fit for I-13 — verified the position NFA for (a|b)*abb accepts aabb, the active set evolving 5→5→10→18 and landing on the final position (bit 16), computed entirely in bitwise AND/OR over integer masks (darts 001/029’s bitwise, paying off). Because it is ε-free with one state per letter, it is the compact way to give I-13 real regular-expression matching: a follow-table of masks and a bounded loop, no pointer graph. Feeds the DFA minimiser (178); the ε-transition route is Thompson (130).