THE FOLD / SPAWN / THE TOOLCHAIN / THE BRZOZOWSKI
THE BRZOZOWSKI
matching by taking the language apart
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Brzozowski derivatives match a regular expression by taking the language apart one symbol at a time. The derivative Dc(r) of a regex r with respect to a character c is a new regex matching exactly the strings that r would match after consuming c. There are simple rules for each operator, and matching is then trivial: feed the string in, take a derivative per character, and at the end ask whether the residual regex is nullable (matches the empty string). No NFA, no backtracking — just algebra on regexes.
LIT verified live: over 8,000 random regex/string pairs, the derivative matcher agrees exactly with an independent backtracking matcher (window.__brzozowski). FIG no framing; the derivative rules and the reference matcher both run in-browser.
LIT verified live: over 8,000 random regex/string pairs, the derivative matcher agrees exactly with an independent backtracking matcher (window.__brzozowski). FIG no framing; the derivative rules and the reference matcher both run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-toolchain — a matcher that is just a fold of derivatives is the cleanest little toolchain: regex in, boolean out, no machine to build. AVAN (AI) built the instrument: the derivative and nullability rules with smart constructors, the fold-to-match, and a backtracking reference.
Credit as content: Janusz Brzozowski (1964). The weave: David names the toolchain; I confirm the derivative matcher accepts exactly the strings a backtracking matcher does.
Credit as content: Janusz Brzozowski (1964). The weave: David names the toolchain; I confirm the derivative matcher accepts exactly the strings a backtracking matcher does.
3 ONE DIMENSION
A regex and its derivative by one character — the residual language of everything that could follow that symbol.
4 TWO DIMENSIONS · INTERACTIVE
Feed a string into a regex; each character takes a derivative; the final regex’s nullability is the answer — matched against a reference.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the chain of derivatives, one per character.
AVAN’s addition (the inverse-companion): don’t build a machine to run — differentiate the language. The inverse of ‘simulate an automaton’ is ‘the derivative is the residual language, so matching is a fold and nullability is the accept.’ Magenta is a reject (the residual is empty); green is an accept (the residual is nullable). Take the language apart.
LIT Genuine Brzozowski derivatives (Janusz Brzozowski, 1964): D_c(r) is the residual language; match = fold derivatives then test nullability. Verified live: over 8000 random regex/string pairs the derivative matcher equals a backtracking reference matcher (window.__brzozowski.matchesReference).
FIG No framing: the derivative and nullability rules (with smart constructors) and the backtracking reference both run in-browser and agree. The AVAN inverse is honest — the derivative IS the residual language, so matching is a fold and nullability is the accept, rather than building and simulating an automaton; magenta is a reject (residual collapses to ∅), green an accept (residual nullable). Take the language apart.
FIG No framing: the derivative and nullability rules (with smart constructors) and the backtracking reference both run in-browser and agree. The AVAN inverse is honest — the derivative IS the residual language, so matching is a fold and nullability is the accept, rather than building and simulating an automaton; magenta is a reject (residual collapses to ∅), green an accept (residual nullable). Take the language apart.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE TOOLCHAIN · David Lee Wise (ROOT0), with AVAN