Lesson 1.3 — Regular-expression derivatives¶

Techniques: Brzozowski derivatives, Antimirov partial derivatives, derivative-based lexer generators (Owens–Reppy–Turon, ml-ulex) · Pebble implements: the Derivative back end of the regex lab (a memoized derivative matcher, which is a lazily built DFA) · Prerequisites: Lessons 1.1 and 1.2 · Time: 4–5 hours

Lessons 1.1 and 1.2 went from an expression to a graph and then ran the graph. Derivatives skip the graph. Ask of \(r_0 = (a \mid b)^{*}abb\): "after reading a, what is left to match?" The answer is again a regular expression, \(bb \mid (a \mid b)^{*}abb\): either this a was the a of abb, or it was one more round of the star. Reading a word symbol by symbol, rewriting the expression each time, and asking at the end "does what is left match the empty word?" decides membership. With a little algebra there are only finitely many such rewritings, and they are the states of a DFA, reached without ever building an NFA.

1. Problem and motivation¶

The problem is the one of Lesson 1.2: decide \(w \in L(r)\), find the longest prefix, or build a DFA for a lexer specification. Derivatives do it by symbolic rewriting of the expression.

Brzozowski derivatives¶

Brzozowski introduced derivatives of regular expressions in 1964 [Brz64] to build sequential circuits from expressions: the derivatives of \(r\) by all words are finitely many up to simple identities, and they form the states of a DFA for \(L(r)\), directly. The method fell out of use for decades, because the graph constructions were thought to be more efficient, until Owens, Reppy and Turon showed it builds DFAs as small as or smaller than the classic route, handles extensions (intersection, complement) for free, and is short to implement [ORT09].

Antimirov partial derivatives¶

A derivative such as \(bb \mid (a \mid b)^{*}abb\) is an alternation, and a DFA state must keep it whole. Antimirov [Ant96] split derivatives into the set of their summands: the partial derivatives. They form the states of an NFA with at most one state more than the expression has symbol positions: a smaller cousin of the position automaton (Lesson 1.1), again built without ε-edges.

Derivative-based lexer generators (Owens–Reppy–Turon)¶

A lexer specification is a vector of expressions (one per token rule). Owens, Reppy and Turon take derivatives of the whole vector at once, add derivative classes so that a large alphabet (bytes, or Unicode) costs one derivative per class instead of one per symbol, and generate the DFA of the whole lexer [ORT09]. This is how the ml-ulex generator of SML/NJ and the ml-lpt tools work. Modern matchers use the same idea: .NET's RegexOptions.NonBacktracking engine is derivative-based.

2. Definitions and algorithms¶

Definition 1.3.1 (Left quotient of a language)

For \(L \subseteq \Sigma^{*}\) and \(u \in \Sigma^{*}\), the left quotient (or residual) is \(u^{-1}L \triangleq \{\, v \mid uv \in L \,\}\). In particular \(w \in L\) iff \(\varepsilon \in w^{-1}L\), and \((ua)^{-1}L = a^{-1}(u^{-1}L)\).

Definition 1.3.2 (Nullability)

\(\nu(r) \triangleq \varepsilon\) if \(\varepsilon \in L(r)\) and \(\emptyset\) otherwise, computed by

\[ \begin{aligned} \nu(\emptyset) &= \nu(a) = \emptyset, & \nu(\varepsilon) &= \nu(r^{*}) = \varepsilon, \\ \nu(r \mid s) &= \nu(r) \mid \nu(s), & \nu(rs) &= \nu(r)\,\nu(s), \end{aligned} \]

reading \(\mid\) and concatenation on \(\{\emptyset, \varepsilon\}\) as "or" and "and".

Definition 1.3.3 (Brzozowski derivative)

For \(a \in \Sigma\) the derivative \(\partial_a r\) is the regular expression

\[ \begin{aligned} \partial_a \emptyset &= \partial_a \varepsilon = \emptyset, & \partial_a b &= \varepsilon \text{ if } b = a \text{ (or } a \in S \text{ for a class } S\text{)}, \ \emptyset \text{ otherwise}, \\ \partial_a (r \mid s) &= \partial_a r \mid \partial_a s, & \partial_a (r s) &= (\partial_a r)\, s \mid \nu(r)\, \partial_a s, \qquad \partial_a (r^{*}) = (\partial_a r)\, r^{*}, \end{aligned} \]

and for words \(\partial_\varepsilon r = r\), \(\partial_{ua} r = \partial_a(\partial_u r)\). The abbreviations desugar first: \(r^{+} = r r^{*}\), \(r? = \varepsilon \mid r\).

Definition 1.3.4 (Similarity and smart constructors)

Similarity \(\approx\) is the least congruence on expressions containing \(r \mid r \approx r\), \(r \mid s \approx s \mid r\), \((r \mid s) \mid t \approx r \mid (s \mid t)\), \(\emptyset \mid r \approx r\), \(\emptyset r \approx r \emptyset \approx \emptyset\), \(\varepsilon r \approx r \varepsilon \approx r\), \((rs)t \approx r(st)\), \((r^{*})^{*} \approx r^{*}\), \(\varepsilon^{*} \approx \emptyset^{*} \approx \varepsilon\). Smart constructors mkAlt, mkCat, mkStar build a canonical representative: they apply these identities, flatten and sort alternatives by a fixed total order, remove duplicates, and (in this course) merge symbol classes in an alternation, \(S \mid T \approx S \cup T\). Two expressions with the same canonical form are similar; similar expressions denote the same language.

Derivatives of the running example

\(\partial_a((a \mid b)^{*}abb) = (\partial_a (a\mid b)^{*})\,abb \mid \nu((a\mid b)^{*})\,\partial_a(abb) = (a\mid b)^{*}abb \mid bb\), which the smart constructors print as bb|[ab]*abb. And \(\partial_b((a \mid b)^{*}abb) = (a\mid b)^{*}abb\) itself: a b at the start never helps to finish abb.

Definition 1.3.5 (Antimirov partial derivatives)

The partial derivative \(\hat\partial_a r\) is a finite set of expressions:

\[ \begin{aligned} \hat\partial_a \emptyset &= \hat\partial_a \varepsilon = \emptyset, & \hat\partial_a b &= \{\varepsilon\} \text{ if } b = a, \ \emptyset \text{ otherwise}, & \hat\partial_a (r \mid s) &= \hat\partial_a r \cup \hat\partial_a s, \\ \hat\partial_a (r s) &= \hat\partial_a(r) \odot s \ \cup\ (\hat\partial_a s \text{ if } \nu(r) = \varepsilon), & \hat\partial_a (r^{*}) &= \hat\partial_a(r) \odot r^{*}, \end{aligned} \]

where \(P \odot s \triangleq \{\, \mathrm{mkCat}(p, s) \mid p \in P \,\}\). For a set \(P\), \(\hat\partial_a P = \bigcup_{p \in P} \hat\partial_a p\).

Definition 1.3.6 (Derivative classes)

A partition \(C(r)\) of \(\Sigma\) is a set of derivative classes for \(r\) if \(a, b\) in the same class implies \(\partial_a r \approx \partial_b r\). Owens–Reppy–Turon compute an approximation from the syntax [ORT09, §4.2]:

\[ \begin{aligned} C(\emptyset) &= C(\varepsilon) = \{\Sigma\}, & C(S) &= \{S, \Sigma \setminus S\}, & C(r \mid s) &= C(r) \wedge C(s), \\ C(r s) &= C(r) \wedge C(s) \text{ if } \nu(r) = \varepsilon, \text{ else } C(r), & C(r^{*}) &= C(r), \end{aligned} \]

where \(P_1 \wedge P_2 = \{\, X \cap Y \mid X \in P_1, Y \in P_2, X \cap Y \neq \emptyset \,\}\) and empty classes are dropped.

Brzozowski derivatives¶

Algorithm 1.3.7 (Derivative matcher)

Input: a regular expression \(r\); a word \(w = a_1 \cdots a_n\).
Output: whether \(w \in L(r)\), and the longest prefix of \(w\) in \(L(r)\).
Precondition: none (the expression is normalized first).
Postcondition: as for Algorithm 1.2.4 (Lemma 1.3.11).
Invariant: after step \(i\), \(L(\mathit{cur}) = (a_1 \cdots a_i)^{-1} L(r)\).

function DerivMatch(r, w):
    cur ← Normalize(r);  last ← (0 if Nullable(cur) else none)
    for i from 1 to n:
        cur ← Deriv(cur, a_i)
        if cur = ∅: break                       # nothing can match any more
        if Nullable(cur): last ← i
    return (last = n, last)

function Deriv(r, a):                           # memoized on (r, a) when r is hash-consed
    case r of
      ∅, ε:   return ∅
      S:      return ε if a ∈ S else ∅
      s | t:  return mkAlt(Deriv(s, a), Deriv(t, a))
      s t:    left ← mkCat(Deriv(s, a), t)
              return mkAlt(left, Deriv(t, a)) if Nullable(s) else left
      s*:     return mkCat(Deriv(s, a), r)

function Normalize(r): rebuild r bottom-up with mkAlt/mkCat/mkStar; s+ → mkCat(s, s*); s? → mkAlt(ε, s)
function Nullable(r): Definition 1.3.2 (memoized per node)
function mkCat(x, y): ∅ if x = ∅ or y = ∅; y if x = ε; x if y = ε;
                      mkCat(x1, mkCat(x2, y)) if x = x1 x2; else the node x y
function mkAlt(x, y): flatten both into a list of alternatives, drop ∅, merge all classes into one,
                      sort by a fixed order, remove duplicates, rebuild right-nested (∅ if empty)
function mkStar(x):   ε if x ∈ {∅, ε}; x if x is already a star; else the node x*

With hash-consed nodes (equal expressions share one node, solutions/labs/ch01-regex/src/Pool.cpp) the memo table from \((r, a)\) to \(\partial_a r\) is a DFA transition table, filled lazily.

Algorithm 1.3.8 (DFA from derivatives, Brzozowski / ORT)

Input: a regular expression \(r\).
Output: a complete DFA \(D\) whose states are canonical expressions.
Precondition: smart constructors implement Definition 1.3.4.
Postcondition: \(L(D) = L(r)\); \(D\)'s states are the dissimilar derivatives of \(r\) (Theorem 1.3.12).
Invariant: every state \(q\) on the worklist or in \(D\) is (similar to) \(\partial_u r\) for some word \(u\); transitions out of processed states are final.

function DerivDFA(r):
    q0 ← Normalize(r);  states ← {q0};  work ← [q0]
    while work not empty:
        q ← pop(work)
        for S in DerivClasses(q):                       # Definition 1.3.6
            q' ← Deriv(q, any symbol of S)
            if q' ∉ states: add q' to states; push(work, q')
            δ(q, a) ← q' for every a in S
    F ← { q ∈ states | Nullable(q) }
    return (states, Σ, δ, q0, F)

Derivatives in .NET's non-backtracking regex engine

Reproduce (dotnet/runtime tag v8.0.0; any OS with curl):

curl -sSfL https://raw.githubusercontent.com/dotnet/runtime/v8.0.0/src/libraries/System.Text.RegularExpressions/src/System/Text/RegularExpressions/Symbolic/SymbolicRegexNode.cs -o srn.cs
grep -n 'private SymbolicRegexNode<TSet> CreateDerivativeWrapper\|internal SymbolicRegexNode<TSet> CreateDerivativeWithoutEffects\|internal List<(SymbolicRegexNode<TSet>, DerivativeEffect\[\])> CreateNfaDerivativeWithEffects' srn.cs
sed -n '1226,1227p;1232p' srn.cs

Output (complete):

1033:        internal SymbolicRegexNode<TSet> CreateDerivativeWithoutEffects(SymbolicRegexBuilder<TSet> builder, TSet elem, uint context) => CreateDerivativeWrapper(builder, elem, context).StripEffects(builder);
1052:        internal List<(SymbolicRegexNode<TSet>, DerivativeEffect[])> CreateNfaDerivativeWithEffects(SymbolicRegexBuilder<TSet> builder, TSet elem, uint context)
1062:        private SymbolicRegexNode<TSet> CreateDerivativeWrapper(SymbolicRegexBuilder<TSet> builder, TSet elem, uint context)
        /// Takes the derivative of the symbolic regex for the given element, which must be either
        /// a minterm (i.e. a class of characters that have identical behavior for all sets in the pattern)
        /// This derivative differs from ones familiar from literature in several ways:

What to notice: RegexOptions.NonBacktracking in .NET 7+ matches by taking derivatives of a symbolic regex node with respect to a minterm, "a class of characters that have identical behavior for all sets in the pattern": a derivative class (Definition 1.3.6) computed exactly rather than approximately. The results are cached as DFA states. The "differs from … literature" comment is about extensions (anchors via context, capture "effects" that reproduce a backtracking engine's choice of match); the core is Algorithm 1.3.7.

Antimirov partial derivatives¶

Algorithm 1.3.9 (Partial-derivative automaton, Antimirov)

Input: a regular expression \(r\) over \(\Sigma\).
Output: an ε-free NFA \(A(r)\) whose states are expressions.
Precondition: \(\Sigma\) finite (or given as derivative classes).
Postcondition: \(L(A(r)) = L(r)\) and \(A(r)\) has at most \(m + 1\) states, \(m\) = number of symbol positions of \(r\) (Theorem 1.3.13).
Invariant: every state is an element of \(\hat\partial_u r\) for some word \(u\).

function PartialDerivAutomaton(r):
    q0 ← Normalize(r);  states ← {q0};  work ← [q0]
    while work not empty:
        q ← pop(work)
        for a in Σ:
            for p in PDeriv(q, a):                      # Definition 1.3.5
                add edge (q, a, p)
                if p ∉ states: add p to states; push(work, p)
    F ← { q | Nullable(q) }
    return (states, Σ, edges, q0, F)

function PDeriv(r, a):
    case r of
      ∅, ε:   return {}
      S:      return {ε} if a ∈ S else {}
      s | t:  return PDeriv(s, a) ∪ PDeriv(t, a)
      s t:    P ← { mkCat(p, t) | p ∈ PDeriv(s, a) }
              return P ∪ PDeriv(t, a) if Nullable(s) else P
      s*:     return { mkCat(p, r) | p ∈ PDeriv(s, a) }

Partial derivatives as NFA states in .NET

Reproduce (dotnet/runtime tag v8.0.0; uses srn.cs from the previous box):

sed -n '1044,1046p;2217p' srn.cs

Output (complete):

        /// are considered and (2) the different elements that would form a top level union are instead returned as separate
        /// nodes (paired with their associated effects). This function is meant to be used for NFA simulation, where top level
        /// unions would be broken up into separate states.
        /// Break up a top level alternation into its elements. This is used when transitioning from DFA mode to NFA mode.

What to notice: for "NFA simulation", CreateNfaDerivativeWithEffects returns "the different elements that would form a top level union" as separate nodes, and when too many DFA states (whole derivatives) accumulate the engine switches to "NFA mode" by breaking a top-level alternation into its elements, tracked as separate states. Those elements are Antimirov's partial derivatives (Definition 1.3.5): an NFA whose size is bounded by the pattern, the same trade as Lesson 1.2's lazy DFA falling back to the Pike VM.

Derivative-based lexer generators (Owens–Reppy–Turon)¶

Algorithm 1.3.10 (Lexer DFA from vectors of derivatives)

Input: a lexer specification: rules \(r_1, \dots, r_k\) in priority order.
Output: a DFA whose states are vectors \((q_1, \dots, q_k)\) of canonical expressions, with accept tag \(\min\{\, i \mid \nu(q_i) = \varepsilon \,\}\).
Precondition: as Algorithm 1.3.8.
Postcondition: in state \(\partial_u(r_1, \dots, r_k)\), rule \(i\) matches \(u\) iff \(\nu(\partial_u r_i) = \varepsilon\); maximal munch then runs on this DFA (Lesson 1.6).
Invariant: each state is \((\partial_u r_1, \dots, \partial_u r_k)\) for some \(u\) (componentwise derivatives).

function LexerDFA(r1, …, rk):
    q0 ← (Normalize(r1), …, Normalize(rk));  states ← {q0};  work ← [q0]
    while work not empty:
        q ← pop(work)
        classes ← C(q1) ∧ … ∧ C(qk)                     # meet of derivative classes
        for S in classes:
            q' ← (Deriv(q1, a), …, Deriv(qk, a)) for any a ∈ S
            if q' ∉ states: add q' to states; push(work, q')
            δ(q, a) ← q' for all a ∈ S
    tag(q) ← min { i | Nullable(qi) } (none if no component is nullable)
    return DFA with start q0, the all-∅ vector as dead state

ml-ulex: the SML/NJ lexer generator is Algorithm 1.3.10

Reproduce (SML/NJ tag v2026.2-rc3; any OS with curl):

B=https://raw.githubusercontent.com/smlnj/smlnj/v2026.2-rc3/tools/ml-lpt/ml-ulex
curl -sSfL $B/lex-gen.sml -o lex-gen.sml
curl -sSfL $B/reg-exp-sig.sml -o reg-exp-sig.sml
sed -n '8p;31p;93p' lex-gen.sml
sed -n '39,42p' reg-exp-sig.sml

Output (complete):

 * DFA generation using RE derivatives
    fun mkDFA startVecs = let
                val edges = RE.derivatives label
    val nullable  : re -> bool
    val derivative : symbol -> re -> re
    val derivatives : re Vector.vector -> 
              ((re Vector.vector) * sym_set) list

What to notice: mkDFA starts from vectors of expressions (one per rule: the "regular vectors" of [ORT09]), and RE.derivatives maps a vector to a list of (derivative vector, symbol set) pairs: one derivative per derivative class, exactly the inner loop of Algorithm 1.3.10. The file's authors are two of the paper's authors.

3. Worked example¶

Brzozowski derivatives¶

One derivative step, rule by rule (the oracle's derivative(..., trace); innermost applications first), for \(\partial_a\) of \(r_0\) = [ab]*abb after normalization:

sub-expression	rule	result
`[ab]`	\(\partial_a S = \varepsilon\) since \(a \in S\)	`ε`
`[ab]*`	\(\partial_a (r^{}) = (\partial_a r) r^{}\)	`[ab]*` (after \(\varepsilon r = r\))
`a`	\(\partial_a a = \varepsilon\)	`ε`
`abb`	\(\partial_a(rs) = (\partial_a r)s\), \(\nu(a) = \emptyset\)	`bb`
`[ab]*abb`	\(\partial_a(rs) = (\partial_a r)s \mid \partial_a s\), \(\nu([ab]^{*}) = \varepsilon\)	`bb\\|[ab]*abb`

The derivative DFA (Algorithm 1.3.8) of \(r_0\) over bytes. Derivative classes split the 256 bytes into a, b and everything else ([^ab], which always leads to \(\emptyset\)):

step	state (canonical expression)	on a	on b	on [^ab]	nullable
1	\(q_0\) = `[ab]*abb`	\(q_1\) new	\(q_0\)	\(\emptyset\) new	no
2	\(\emptyset\)	\(\emptyset\)	\(\emptyset\)	\(\emptyset\)	no
3	\(q_1\) = `bb\\|[ab]*abb`	\(q_1\)	\(q_2\) new	\(\emptyset\)	no
4	\(q_2\) = `b\\|[ab]*abb`	\(q_1\)	\(q_3\) new	\(\emptyset\)	no
5	\(q_3\) = `[ab]*abb\\|ε`	\(q_1\)	\(q_0\)	\(\emptyset\)	yes

The worklist is empty after step 5. Five states: \(q_0, \dots, q_3\) and the dead state. This is already the minimal DFA (Lesson 1.4 computes the same four live states by minimizing the subset construction's five). Membership of aabb: \(q_0 \xrightarrow{a} q_1 \xrightarrow{a} q_1 \xrightarrow{b} q_2 \xrightarrow{b} q_3\), and \(q_3\) is nullable, so aabb \(\in L(r_0)\).

Try it

./course drill brzozowski-derivative --seed 3 --difficulty medium, then --solution for the rule-by-rule trace.

Antimirov partial derivatives¶

\(\hat\partial_a(\texttt{[ab]*abb}) = \{\,\texttt{bb},\ \texttt{[ab]*abb}\,\}\) (the two summands of the Brzozowski derivative, now separate states) and \(\hat\partial_b(\texttt{[ab]*abb}) = \{\texttt{[ab]*abb}\}\). The worklist continues with bb (\(\hat\partial_b = \{\texttt{b}\}\)), b (\(\{\varepsilon\}\)) and \(\varepsilon\) (no successors):

state	on a	on b	final
→ 0 `[ab]*abb`	{0, 1}	{0}
1 `bb`	{}	{2}
2 `b`	{}	{3}
3 `ε`	{}	{}	yes

Four states, ε-free: smaller than the six-state position automaton of Lesson 1.1 (whose states 0, 1, 2 collapse into state 0 here) and the textbook "obvious" NFA for "ends in abb".

Derivative-based lexer generators (Owens–Reppy–Turon)¶

Rules \(r_1\) = if (priority 1) and \(r_2\) = [a-z]+ (priority 2). States are pairs:

state	vector	derivative classes (meet)	transitions	tag
0	(`if`, `[a-z][a-z]*`)	`i`, `[a-hj-z]`, `[^a-z]`	i → 3, other letters → 2, non-letters → 1	–
1	(∅, ∅)	all bytes	→ 1 (dead)	–
2	(∅, `[a-z]*`)	`[a-z]`, `[^a-z]`	letters → 2, else → 1	rule 2
3	(`f`, `[a-z]*`)	`f`, `[a-eg-z]`, `[^a-z]`	f → 4, other letters → 2, else → 1	rule 2
4	(ε, `[a-z]*`)	`[a-z]`, `[^a-z]`	letters → 2, else → 1	rule 1 (both nullable; rule 1 has priority)

Five states for "keyword if or identifier". Reading iff: \(0 \to 3 \to 4 \to 2\), tag rule 2 (an identifier); reading if: \(0 \to 3 \to 4\), tag rule 1 (the keyword). The vector makes priority and maximal munch fall out of \(\nu\).

4. Invariants and correctness¶

Brzozowski derivatives¶

Lemma 1.3.11 (Nullability and the derivative are sound)

For every expression \(r\) and symbol \(a\): \(\nu(r) = \varepsilon\) iff \(\varepsilon \in L(r)\), and \(L(\partial_a r) = a^{-1} L(r)\). Consequently \(L(\partial_u r) = u^{-1}L(r)\) for every word \(u\), and \(w \in L(r)\) iff \(\nu(\partial_w r) = \varepsilon\).

Proof

Both claims by structural induction on \(r\). Nullability: \(\varepsilon \in L(r \mid s)\) iff it is in one of them; \(\varepsilon \in L(rs)\) iff it is in both (a split of ε is ε·ε); \(\varepsilon \in L(r^{*})\) always; base cases are immediate. Derivative: \(a^{-1}\{b\} = \{\varepsilon\}\) if \(b = a\) else \(\emptyset\); \(a^{-1}(L_1 \cup L_2) = a^{-1}L_1 \cup a^{-1}L_2\). For concatenation, \(av \in L(r)L(s)\) iff either \(av = (au)v'\) with \(au \in L(r)\), \(v' \in L(s)\), i.e. \(v \in (a^{-1}L(r))L(s)\); or the \(r\)-part is ε (so \(\varepsilon \in L(r)\)) and \(av \in L(s)\), i.e. \(v \in a^{-1}L(s)\). This is \(L((\partial_a r)s \mid \nu(r)\partial_a s)\) by induction. For the star, a nonempty word \(av\) of \(L(r)^{*}\) starts with a nonempty first factor \(au \in L(r)\) followed by a word of \(L(r)^{*}\): \(v \in (a^{-1}L(r))\,L(r)^{*} = L((\partial_a r) r^{*})\). Smart constructors only apply identities that preserve languages (Definition 1.3.4). The word version follows by induction on \(\lvert u \rvert\) with Definition 1.3.1, and the membership test is the case \(v = \varepsilon\). \(\square\)

Theorem 1.3.12 (Brzozowski: finitely many dissimilar derivatives)

For every \(r\), the set \(\{\, \partial_u r \mid u \in \Sigma^{*} \,\}\) is finite up to similarity (Definition 1.3.4). Hence Algorithm 1.3.8 terminates, and it produces a DFA with \(L(D) = L(r)\).

Proof sketch (full proof: [Brz64, Theorem 5.2]; for the smart-constructor version [ORT09, §3])

By induction on \(r\), show that every derivative of \(r\) is similar to an expression of a fixed finite form. Symbols, ε, ∅ have at most three derivatives. For \(r \mid s\): \(\partial_u(r \mid s) = \partial_u r \mid \partial_u s\), a pair drawn from two finite sets. For \(rs\): \(\partial_u(rs)\) is similar to \((\partial_u r)s \mid \partial_{v_1} s \mid \cdots \mid \partial_{v_j} s\), where \(v_1, \dots, v_j\) are suffixes of \(u\); because \(\mid\) is idempotent, commutative and associative under \(\approx\), the alternatives form a set of derivatives of \(s\), finitely many sets. For \(r^{*}\): \(\partial_u(r^{*})\) is similar to a union of terms \((\partial_{v} r)r^{*}\), again a subset of a finite set. The idempotence and ACI rules are essential: without them the same derivative can appear with ever more duplicate alternatives (§5). Termination of the worklist follows, and \(L(D) = L(r)\) by Lemma 1.3.11: the state reached on \(w\) is \(\partial_w r\), final iff nullable.

Antimirov partial derivatives¶

Theorem 1.3.13 (Antimirov)

(i) \(L(\partial_a r) = \bigcup_{p \in \hat\partial_a r} L(p)\). (ii) The set of all partial derivatives of \(r\) by all words has at most \(m + 1\) elements, where \(m\) is the number of symbol positions of \(r\) (after desugaring \(^{+}\) and \(?\), which can duplicate positions). (iii) \(L(A(r)) = L(r)\).

Proof sketch (full proof: [Ant96, Theorems 2 and 3])

(i) By structural induction, parallel to Lemma 1.3.11: each rule of Definition 1.3.5 splits the corresponding rule of Definition 1.3.3 into its summands. (ii) Every partial derivative by a nonempty word has the form \(\varepsilon\) or \(p_{\text{pos}} \cdot s_1 \cdots s_k\) where the head is "what remains after a particular symbol position" (the suffix of the expression that follows that position): one term per position, plus \(r\) itself for the empty word. So there are at most \(m + 1\). (iii) By (i) and induction on \(\lvert w \rvert\), the union of the languages of the states reachable on \(w\) is \(w^{-1}L(r)\); \(w\) is accepted iff one of them is nullable.

Derivative-based lexer generators (Owens–Reppy–Turon)¶

Proposition 1.3.14 (Derivative classes are sound)

If \(a, b\) lie in the same class of \(C(r)\) (Definition 1.3.6), then \(\partial_a r = \partial_b r\) syntactically (before and after the smart constructors). Hence Algorithm 1.3.8 computes one derivative per class and still builds the full DFA, and Algorithm 1.3.10 is correct componentwise with the meet of the classes.

Proof

Structural induction. For a class \(S\): two symbols both in \(S\) give ε, both outside give ∅. For \(r \mid s\): a class of \(C(r) \wedge C(s)\) lies inside one class of each, so both components agree by induction. For \(rs\) with \(\nu(r) = \emptyset\): \(\partial_a(rs) = (\partial_a r)s\) depends only on \(\partial_a r\), constant on classes of \(C(r)\); with \(\nu(r) = \varepsilon\) both \(\partial_a r\) and \(\partial_a s\) are constant on classes of the meet. For \(r^{*}\): \((\partial_a r)r^{*}\) depends only on \(\partial_a r\). For vectors, a class of the meet \(\bigwedge_i C(q_i)\) lies inside a class of every \(C(q_i)\). The partition may be finer than necessary (hence "approximate"): two classes can still have equal derivatives, which costs a redundant computation but not correctness. \(\square\)

5. Complexity¶

Variables: \(n = \lvert w \rvert\); \(m\) = symbol positions of \(r\); \(\lvert r \rvert\) = syntax-tree size; \(d\) = number of dissimilar derivatives; \(k\) = number of derivative classes per state.

Technique	Matching time	Build	States	Notes
Brzozowski, memoized	\(O(n)\) after warm-up; first visit to a state costs \(O(\lvert \partial \rvert)\)	\(O(d \cdot k)\) derivatives	\(d \le 2^{O(\lvert r \rvert)}\) (like any DFA)	canonicalization and hashing dominate the constant
Brzozowski, unmemoized	\(O(n \cdot \lvert \partial \rvert)\), derivatives can grow	none	–	only for tiny inputs
Antimirov	\(O(n \cdot m^{2})\) as an NFA simulation	\(O(m^{2}\lvert\Sigma\rvert)\) edges	\(\le m + 1\)	ε-free NFA, no subset explosion
ORT lexer (vectors + classes)	\(O(n)\) (DFA)	\(O(d \cdot k)\) vector derivatives	about the size of the subset construction's DFA, often smaller [ORT09]	classes make large alphabets cheap

Proposition 1.3.15 (Without similarity, derivatives grow exponentially)

Let \(r = (a^{*})^{*}\). Using the rules of Definition 1.3.3 with only the \(\emptyset\)/\(\varepsilon\) unit laws for concatenation and \(\emptyset \mid x = x\) (no idempotence or commutativity), \(\lvert \partial_{a^{k}} r \rvert\) at least doubles with each \(k\); with the full smart constructors, \(\partial_{a^{k}} r = a^{*}(a^{*})^{*}\) for all \(k \ge 1\).

Proof

Write \(s = (a^{*})^{*}\) and \(D\) for the derivative by \(a\) with only the unit laws. \(D(a^{*}) = \mathrm{mkCat}(\varepsilon, a^{*}) = a^{*}\), so \(t_1 = D(s) = \mathrm{mkCat}(D(a^{*}), s) = a^{*}s\), of size \(2 + 3 + 1 = 6\). Since \(a^{*}\) is nullable, \(D(t_1) = \mathrm{mkCat}(D(a^{*}), s) \mid D(s) = t_1 \mid t_1\). By induction, if \(t_k = x \mid x\) then \(D(t_k) = D(x) \mid D(x)\), so \(t_{k+1} = t_k \mid t_k\) and \(\lvert t_{k+1} \rvert = 2\lvert t_k \rvert + 1\), i.e. \(\lvert t_k \rvert = 7 \cdot 2^{k-1} - 1\): at least doubling. With idempotence, \(t_1 \mid t_1 \approx t_1\), so \(t_k = t_1 = a^{*}(a^{*})^{*}\) for every \(k \ge 1\), which the smart constructors print as a*a**. \(\square\)

Measured with the oracle (sizes = syntax-tree nodes of \(\partial_{a^{k}}((a^{*})^{*})\), \(k = 1..8\)):

rules used	\(k=1\)	2	3	4	5	6	7	8
none (raw Definition 1.3.3)	8	22	50	106	218	442	890	1786
∅/ε units only	6	13	27	55	111	223	447	895
full similarity (Definition 1.3.4)	6	6	6	6	6	6	6	6

Pathological input for the DFA (with similarity) is the same family as for the subset construction: \((a\mid b)^{*}a(a\mid b)^{k-1}\) has \(2^{k}\) dissimilar derivatives, because it has \(2^{k}\) distinct residuals (Proposition 1.2.11).

At scale. In the lab (ch01-regexbench, 1.8 MB of short lines), the memoized derivative matcher runs at 5–13 ms, between the precomputed DFA (2–4 ms) and the Pike VM (36–106 ms): after warm-up every step is a hash lookup. [ORT09] compare the DFAs that ml-ulex builds with derivatives against those of the subset construction on real lexer specifications and find them of about the same size or smaller, without a separate minimization pass.

Brzozowski derivatives¶

Extended operators [ORT09, Brz64]: \(\partial_a(r \,\&\, s) = \partial_a r \,\&\, \partial_a s\) and \(\partial_a(\neg r) = \neg \partial_a r\) make intersection and complement free, which is hard with Thompson NFAs.
Symbolic derivatives (.NET's SRM): take the derivative with respect to a predicate (a character set) rather than a symbol, which is Definition 1.3.6 pushed into the data structure; needed for Unicode.
Derivatives with effects / backtracking simulation (.NET 7): record capture updates on derivative edges to report the same match a backtracking engine would.

Antimirov partial derivatives¶

Partial-derivative automaton vs position automaton: the former is a quotient of the latter (Champarnaud–Ziadi), so never larger; both are ε-free and \(O(m)\)-state.
Partial derivatives for NFA mode (.NET): when the DFA cache overflows, break derivatives into their partial derivatives and simulate an NFA (box in §2).
Submatching with partial derivatives (Sulzmann–Lu): each partial derivative carries a parse-tree builder, giving POSIX submatches.

Derivative-based lexer generators (Owens–Reppy–Turon)¶

Regular vectors give priority for free: the tag is the first nullable component; ties disappear.
Approximate vs exact derivative classes: exact classes would require comparing derivatives; approximations (Definition 1.3.6) are cheap and rarely much finer.
Unicode: classes over code points instead of bytes keep the DFA small for UTF-8 identifier rules (Lesson 1.9), at the cost of decoding before the table lookup.

7. In real compilers¶

Brzozowski derivatives¶

.NET System.Text.RegularExpressions/.../Symbolic/SymbolicRegexNode.cs — CreateDerivativeWrapper, CreateDerivativeWithoutEffects (dotnet/runtime v8.0.0) [DOTNET-SRM]; box in §2.
The course lab solutions/labs/ch01-regex/src/Pool.cpp — Pool::derivative with hash-consing and memoization.

No mainstream C/C++/Rust compiler lexer uses derivatives: they are hand-written (Lesson 1.5).

Antimirov partial derivatives¶

.NET "NFA mode": CreateNfaDerivativeWithEffects and EnumerateAlternationBranches in the same file [DOTNET-SRM]; box in §2.
The course oracle tools/course/lib/regex.py — partial_derivatives, antimirov_nfa.

Derivative-based lexer generators (Owens–Reppy–Turon)¶

SML/NJ ml-ulex tools/ml-lpt/ml-ulex/lex-gen.sml — mkDFA over vectors, RE.derivatives (tag v2026.2-rc3) [ML-ULEX]; box in §2. ml-ulex also generates lexers for ml-lex specifications, so SML/NJ's own tools are built with it.

8. Comparison¶

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
Brzozowski derivatives	any regex, plus \(\&\) and \(\neg\) for free	\(O(n)\) memoized; DFA as small or smaller than subset construction	states are readable expressions ("what is left to match")	small: one function per operator + smart constructors	lazy matching (.NET NonBacktracking), teaching, extended regexes
Antimirov partial derivatives	any regex	NFA simulation, \(\le m + 1\) states	states are expression suffixes	small	NFA fallback (.NET), submatching research
ORT derivative lexer generators	lexer specifications with priority	\(O(n)\) DFA; build proportional to states × classes	DFA states map back to rule suffixes	moderate (vectors, classes, codegen)	ml-ulex (SML/NJ)

Choose derivatives when you want a DFA without an NFA, need intersection or complement, or want a lazy matcher whose states are self-describing. Choose partial derivatives when you need an ε-free NFA of guaranteed small size. Choose the ORT generator design when you write a lexer generator: it handles priority, large alphabets and minimal-ish DFAs in one mechanism.

9. Assessment¶

Technique	Quiz ids	Drill	Flashcard tag	Exercises
Brzozowski derivatives	`derivative-compute`, `derivative-nullable`	`./course drill brzozowski-derivative`	`brzozowski-derivatives`	Lab L4
Antimirov partial derivatives	`antimirov-bound`, `derivative-compute`	`./course drill brzozowski-derivative --difficulty hard` (split each answer into its summands)	`antimirov`	—
Derivative-based lexer generators (Owens–Reppy–Turon)	`ort-lexer-tag`, `derivative-classes`	`./course drill maximal-munch` (the same DFA, built any way)	`derivative-lexers`	—

Pitfall

Derivatives are finite only up to similarity. An implementation that forgets r|r = r or does not sort alternatives will loop forever building "new" states that differ only in duplicate or reordered alternatives (Proposition 1.3.15).

References¶

See the chapter references.

Lesson 1.3 — Regular-expression derivatives¶

1. Problem and motivation¶

Brzozowski derivatives¶

Antimirov partial derivatives¶

Derivative-based lexer generators (Owens–Reppy–Turon)¶

2. Definitions and algorithms¶

Brzozowski derivatives¶

Antimirov partial derivatives¶

Derivative-based lexer generators (Owens–Reppy–Turon)¶

3. Worked example¶

Brzozowski derivatives¶

Antimirov partial derivatives¶

Derivative-based lexer generators (Owens–Reppy–Turon)¶

4. Invariants and correctness¶

Brzozowski derivatives¶

Antimirov partial derivatives¶

Derivative-based lexer generators (Owens–Reppy–Turon)¶

5. Complexity¶

6. Variants and refinements¶

Brzozowski derivatives¶

Antimirov partial derivatives¶

Derivative-based lexer generators (Owens–Reppy–Turon)¶

7. In real compilers¶

Brzozowski derivatives¶

Antimirov partial derivatives¶

Derivative-based lexer generators (Owens–Reppy–Turon)¶

8. Comparison¶

9. Assessment¶

References¶