Regex Derivatives
A regular expression matched against a string, one character at a time, via Brzozowski derivatives.
Presets
About this match
How to use this
Type a regex on the left and a string on the right. The comic strip above shows the regex transforming character by character: each card is the regex that remains after consuming one more character of the input. A green dot marks any step where the regex is nullable, meaning the empty string is a valid completion. If the final card is nullable, the whole input matches.
The view toggle switches between the comic strip (every step at once) and a single-tree view that shows one step's regex as a structural tree, with a slider to scrub through the steps. The show toggle switches between simplified derivatives, which collapse algebraic noise like ε·R and R+R, and raw derivatives, which let you watch the trees grow without the cleanup pass.
Things to notice: how the regex sometimes returns to its starting shape after a successful loop, how a single ∅ in any card kills the match for good and the early exit fires, and how the simplification pass keeps the trees readable — switch to raw on a regex with alternation under a star and watch the noise pile up.
Is this actually new?
No. Janusz Brzozowski published "Derivatives of Regular Expressions" in the Journal of the ACM in 1964. Owens, Reppy and Turon's 2009 paper "Regular-expression derivatives reexamined" revived the technique academically and is the modern canonical reference. Matt Might extended it to context-free grammars in 2011 with "Yacc is dead". Adam Chlipala teaches it in his Coq textbook. Production regex engines built on derivatives include .NET's RegexOptions.NonBacktracking (2023, with a PLDI paper), ocaml-re, and Google's redgrep. Walter Schulze wrote a charming Pac-Man-themed pedagogical introduction. Chengsong Tan and Christian Urban presented "POSIX Lexing with Bitcoded Derivatives" at ITP 2023.
What this page is: the Brzozowski algorithm made tactile. The compiler runs in your browser and the derivative trace is the matching trace — there is no separate state machine, no compilation phase, and no backtracking. The wobble worth knowing about: the "one operator" lives in the matcher, not in the regex itself. The regex is still built from |, ·, *, +, ?, ε, and ∅. The squeeze is that all matching reduces to one operation, the derivative, applied to that regex one character at a time.