THE FOLD / BOSS / THE FINAL BOSS / THE GLUSHKOV
THE GLUSHKOV
a regex becomes a walk over letter-positions
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Glushkov’s construction turns a regular expression into a position automaton: give every letter-occurrence in the regex a number (position), then compute three sets — First (positions a match can start on), Last (positions it can end on), and Follow (which position can come after which). The result is an NFA with exactly one state per letter-position and no epsilon-transitions at all. Matching is then a single left-to-right sweep that carries a set of currently-active positions — no backtracking, no exponential blowup. It is the clean bridge from ‘a pattern’ to ‘a machine that recognizes it.’
LIT verified live: for nine regexes, the Glushkov automaton’s accept/reject decision matches an independent reference matcher on every string over {a,b,c,d} up to length 5 — thousands of (regex, string) pairs, zero disagreements (window.__glushkov). FIG no framing; the parser, the First/Last/Follow construction, the set-sweep, and the reference matcher all run in-browser.
LIT verified live: for nine regexes, the Glushkov automaton’s accept/reject decision matches an independent reference matcher on every string over {a,b,c,d} up to length 5 — thousands of (regex, string) pairs, zero disagreements (window.__glushkov). FIG no framing; the parser, the First/Last/Follow construction, the set-sweep, and the reference matcher all run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-final-boss — the accepting machine at the end of the pattern: reach a Last position and the gate opens. AVAN (AI) built the instrument: the regex parser, nullable/First/Last/Follow, the epsilon-free position NFA, the set-sweep matcher, and a reference matcher to check it against.
Credit as content: Victor M. Glushkov (1961). The weave: David names the final boss; I confirm the position automaton accepts exactly the same language as the reference on every string tested.
Credit as content: Victor M. Glushkov (1961). The weave: David names the final boss; I confirm the position automaton accepts exactly the same language as the reference on every string tested.
3 ONE DIMENSION
The regex /a(b|c)*d/ as a position automaton: one state per letter, blue arcs are Follow, orange rings are accepting.
4 TWO DIMENSIONS · INTERACTIVE
Cycle through test words; each is accepted or rejected by the automaton and checked against the reference matcher.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the language the automaton accepts.
AVAN’s addition (the inverse-companion): don’t ask ‘does it match?’ — carry the set. The inverse of ‘a pattern’ is ‘the set of active positions after each letter; a word is accepted iff that set ever contains a Last position.’ Magenta is everything rejected; green is the accepted language. A pattern turned inside-out into a walk.
LIT Genuine Glushkov position-automaton construction (Victor M. Glushkov, 1961). Verified live: for 9 regexes the epsilon-free position NFA's accept/reject decision matches an independent reference matcher on every string over {a,b,c,d} up to length 5 (thousands of (regex,string) pairs, zero disagreements) (window.__glushkov.matches, .tested).
FIG No framing; the parser, the First/Last/Follow construction, the set-sweep, and the reference matcher all run in-browser. The AVAN inverse is honest — instead of asking 'does it match?', carry the set of active positions after each letter; a word is accepted iff that set ever contains a Last position. Magenta is everything rejected; green is the accepted language. A pattern turned inside-out into a walk.
FIG No framing; the parser, the First/Last/Follow construction, the set-sweep, and the reference matcher all run in-browser. The AVAN inverse is honest — instead of asking 'does it match?', carry the set of active positions after each letter; a word is accepted iff that set ever contains a Last position. Magenta is everything rejected; green is the accepted language. A pattern turned inside-out into a walk.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE FINAL BOSS · David Lee Wise (ROOT0), with AVAN