Differentiating a Regular Expression: Residual Languages as Automaton States

Take a regular expression and a single character. There is an operation that returns the expression describing what remains to be matched after that character: the derivative. Apply it once per input symbol and the expression shrinks toward either the empty-string expression or the empty language. Matching becomes a fold, and the set of expressions encountered along the way is the state set of a deterministic automaton, with no epsilon transitions and no subset construction anywhere.

The construction is older than most treatments of automata theory would suggest, and it has a property that the Thompson route lacks: each state is a residual language, the set of strings still acceptable from that point. That makes the machine canonical by construction, and it also makes the state count sensitive to how the expressions are normalized.

The derivative, case by case

For a language L and a symbol a, the derivative is D_a(L) = { w : aw ∈ L }. For regular expressions the operation is defined structurally:

• D_a(∅) = ∅, D_a(ε) = ∅.
• D_a(b) = ε if b = a, and ∅ otherwise, for a single symbol b.
• D_a(R ∪ S) = D_a(R) ∪ D_a(S).
• D_a(R · S) = D_a(R) · S ∪ D_a(S) if R can match the empty string, and D_a(R) · S otherwise.
• D_a(R*) = D_a(R) · R*.

The concatenation rule is the only subtle one. Consuming a might match inside R, leaving D_a(R) followed by S. It might also be that R matches the empty string, in which case a could begin the S part, leaving D_a(S). Both possibilities must be kept, which is why the rule is a union and why it depends on nullability.

The star rule has no union because the loop can always be re-entered: after consuming one repetition’s worth of input, the star remains available.

Nullability is the predicate ν(R) that holds when ε ∈ L(R): true for ε and for R*, false for ∅ and single symbols, the conjunction for concatenation, and the disjunction for union. It is computed by the same structural recursion and is the second half of the matching procedure.

# Nodes: ('nil',), ('emp',), ('sym', c), ('cat', r, s), ('alt', r, s), ('star', r)

def nullable(r):
    k = r[0]
    if k in ('emp', 'star'): return True
    if k in ('nil', 'sym'):  return False
    if k == 'cat': return nullable(r[1]) and nullable(r[2])
    return nullable(r[1]) or nullable(r[2])          # alt

def deriv(r, c):
    k = r[0]
    if k == 'nil':  return ('nil',)
    if k == 'emp':  return ('nil',)
    if k == 'sym':  return ('emp',) if r[1] == c else ('nil',)
    if k == 'alt':  return alt(deriv(r[1], c), deriv(r[2], c))
    if k == 'cat':
        left = cat(deriv(r[1], c), r[2])
        if nullable(r[1]):
            return alt(left, deriv(r[2], c))         # a may start the right operand
        return left
    return cat(deriv(r[1], c), r)                    # star: derivative of the body, then loop

def matches(r, s):
    for c in s:
        r = deriv(r, c)
        if r[0] == 'nil':
            return False                             # no continuation can revive the empty language
    return nullable(r)

The early exit on nil is an optimization that follows from the definition: once the derivative is the empty language, every further derivative is also empty, so the rest of the input cannot change the verdict. It costs nothing and avoids work on rejecting inputs.

Why the states come out deterministic

Each derivative is a regular expression denoting a residual language, and the transition from one expression to the next is a function of the symbol alone. There is no choice to make and no set to carry, so the machine whose states are expressions is deterministic by construction. This is the difference between the derivative approach and the Thompson approach: Thompson builds a nondeterministic machine and then either simulates sets, as in set-based NFA simulation, or determinizes it through the subset construction, while derivatives produce the deterministic machine directly.

The state count is the number of distinct residual languages reachable from the initial expression. If two derivatives denote the same language, they are the same state, and the construction should merge them. Merging is not automatic, because expressions are syntax and residuals are semantics: two syntactically different expressions can denote the same language, and a memo table keyed on syntax will keep them apart.

That gap is where the engineering lives. A practical implementation keys the memo table on a normalized form of the expression, using the algebraic laws that hold for the constructors:

• Union is associative, commutative, and idempotent: R ∪ R = R, R ∪ ∅ = R.
• Concatenation is associative with ε as identity: ε · R = R, R · ε = R, ∅ · R = ∅.
• Star satisfies ∅* = ε, ε* = ε, and (R*)* = R*.

Applying these laws at construction time, via smart constructors, collapses many syntactically distinct derivatives into one canonical node. It does not collapse all of them, because the laws do not capture language equality in general: (a ∪ b)* and (a* b*)* are the same language and normalize to different trees. Implementations accept that residue of duplication, or they add a decision procedure for equivalence, which brings back the cost the derivative approach was avoiding.

The blow-up, and how it is bounded

Brzozowski’s original result bounds the number of distinct derivatives of an expression with n symbols and operators: the reachable residuals are at most 2^n, and the bound is attained by expressions built to encode every subset of a set of positions. The mechanism is the same one that makes determinization exponential: an expression with n alternatives that can be entered independently needs a residual for every combination of the alternatives that are still live.

In practice the residual count for expressions written by hand stays small, usually the same order as the number of distinct positions in the pattern, which is linear in the pattern’s size. The exponential case requires an expression designed to have it, typically a nested alternation of the form that encodes the “k-th symbol from the end” language, whose minimal DFA has 2^k states. Any correct construction of the minimal machine for that language must produce those states, so the derivative method is not at fault; it is simply not exempt.

Memoization changes the cost profile rather than the count. With a table of expressions already seen, each input symbol costs one table lookup plus, for the first visit to a state, one derivative computation per symbol, which is proportional to the size of the expression node. The total work is the number of states times the alphabet size times the expression size, and the table is the machine. For an expression of 100 nodes and 200 reachable residuals, the table has 200 rows and the per-symbol cost during a scan is one lookup.

Comparing with the automaton route

The Thompson route produces a machine with at most 2n states for an n-symbol expression, and that machine is nondeterministic. Determinizing it may multiply the state count, and minimizing it requires a refinement pass. The derivative route produces a deterministic machine with up to 2^n states, and if the normalization is complete enough, that machine is already minimal.

Property	Thompson plus determinization	Derivatives
Intermediate machine	epsilon NFA, at most 2n states	none
Deterministic output	after subset construction	immediately
States for a small pattern	often fewer	more, unless normalized
Submatch support	needs tagged transitions	needs annotated expressions
Reuse of the pattern	compile once, run many times	derivative per state, memoized

The derivative method wins when the pattern changes frequently and the input is short, because the machine is built incrementally as input arrives and no separate compilation step exists. It loses when the pattern is fixed and the input is long, because a precomputed table is one load per symbol while a derivative computation is a tree traversal.

Derivatives and minimization

There is a second use of the derivative, unrelated to matching. Brzozowski’s minimization algorithm reverses a DFA to get an NFA, determinizes it, reverses again, and determinizes once more. The result is the minimal DFA for the language, and the argument is that the intermediate machines’ states are residual languages of the reversed language, so the reachable set after the second determinization is exactly the set of distinct residuals.

The algorithm is elegant and its bound is the product of the two determinizations, which can be far worse than the O(n log n) of partition refinement. Its value is as a specification: it produces the minimal machine without any notion of state equivalence, using only reversal and subset construction, and it is therefore easy to verify. Implementations that need the minimal machine for large inputs use refinement, and the double-reversal construction is used to check refinement’s output in tests, where its slowness does not matter.

The two views agree on the same object. The states of the minimal machine are the classes of the right congruence, as the Myhill-Nerode theorem states, and a residual language is exactly a right context. Differentiation computes one right context per step; refinement computes all of them at once from a machine. Neither is more fundamental, and the choice between them is a choice about which representation of the language is available at the start.