◄ WORLD V · SONNY 5DART 177 · a helldive at the net

THE BRZOZOWSKI DERIVATIVE the state is the rest of the pattern after a letter

The derivative of a regular expression with respect to a symbol is “what pattern remains after consuming that symbol.” Match a string by taking derivatives one letter at a time; accept if the final expression is nullable (matches the empty string). The genius: the states of the DFA are the derivatives themselves — regexes as states, computed on demand, no separate NFA-to-DFA machinery at all.

THE TECHNIQUE d/da(r), then nullable? = accept

Match a*b by derivatives. d/da(a*b) = a*b (the star loops, same state); d/db(a*b) = ε (nullable — accept). Three derivatives are the three DFA states. Watch the pattern transform letter by letter: live demo







  
HISTORY & CREDIT Janusz Brzozowski, JACM 1964

  
“Derivatives are just another way to write the subset construction.” — no. There is no NFA in sight: the derivative is a direct, algebraic regex-to-DFA map where each state is a regular expression, and it extends cleanly to intersection and complement (which the NFA route makes awkward). cited

  
1964 · Janusz Brzozowski — “Derivatives of regular expressions” (JACM 11(4)): the derivative operator and the direct DFA construction, states = derivatives up to similarity.
1962 · Brzozowski — the double-reversal DFA minimisation (reverse, determinise, reverse, determinise), a separate famous result from his earlier “Canonical Regular Expressions and Minimal State Graphs for Definite Events” — it predates the derivatives paper.
2009 · Owens, Reppy & Turon — “Regular-expression derivatives reexamined”: the functional-programming revival, showing derivatives are the cleanest way to build a scanner.

  
Finiteness needs one trick: quotient the derivatives by similarity (associativity/commutativity/idempotence of +), or the set of derivatives is infinite — Brzozowski proved that under similarity it is finite, so the DFA terminates. Brzozowski 1964






  
RECOMMEND FOR I-13 states are derivatives, computed

  
Matching a*b by derivatives runs on the canonical compiler — the three derivative-states, accept by nullability:

  
$ i13 run brz.i13   # a*b: states 0=a*b, 1=eps(nullable), 2=empty(dead)
aab -> derivative state 1   nullable = 1   ACCEPT
aa  -> derivative state 0   nullable = 0   reject (no b consumed)

  
Recommend: the Brzozowski derivative is LIT and the cleanest matcher for I-13 — verified a*b matches aab (ends in the nullable derivative ε) and rejects aa (ends in a*b, not nullable), the derivative-states run as a small transition table with a nullable flag. Because the states are the derivatives — computed on demand, not stored ahead of time — it is a natural fit for a language that prizes computed-not-stored (the Stern-Brocot axis, dart 092): the DFA is generated lazily as input arrives. It also gives intersection and complement for free, which the NFA route (176) does not.