Lesson 1.4 — DFA minimization and the Myhill–Nerode theorem¶

Techniques: Moore's partition refinement, Hopcroft's \(O(kn \log n)\) algorithm, Brzozowski's double reversal; the theory behind all three is the Myhill–Nerode theorem · Pebble implements: all three in the regex lab (minimalDFASize, R6; Hopcroft is required, Moore and Brzozowski are ★ tests) · Prerequisites: Lesson 1.2 · Time: 4–6 hours

The subset construction of Lesson 1.2 turned the Thompson NFA of \(r_0 = (a \mid b)^{*}abb\) into five states, A–E. Two of them are redundant: A and C both mean "nothing useful seen yet", have the same transitions (B on a, C on b) and are both non-accepting. Merge them and the DFA does the same job with four states. For a lexer every state is a row of a table in the binary, so fewer states is smaller and faster code. This lesson makes "the same job" precise, proves that the smallest DFA is unique, and gives three algorithms that find it.

1. Problem and motivation¶

Given a complete DFA \(A\), find a DFA \(A'\) with \(L(A') = L(A)\) and as few states as possible. For lexers, the input is the subset-constructed DFA of all token rules together, and "accepting" is refined to "accepting rule \(i\)", so the partition must also keep different rules apart.

Moore's algorithm¶

Moore's 1956 "Gedanken-experiments" [Moo56] asked which states of a sequential machine an experimenter can tell apart by feeding inputs and watching outputs. His answer is an iteration: start with "accepting vs not", and keep splitting groups whose members go to different groups on some symbol. It is simple, and it is the default minimizer of re2c.

Hopcroft's algorithm¶

Moore's method can take \(\Theta(n)\) rounds of \(\Theta(kn)\) work each. Hopcroft [Hop71] reorganized the same refinement around splitters, processed from a worklist, with the rule "after a split, only the smaller half needs to be processed again", which gives \(O(kn\log n)\). Gries [Gri73] and Knuutila [Knu01] rewrote the proof in modern form. It is the minimizer of Rust's regex-automata and of most automata libraries.

Brzozowski's double reversal¶

Brzozowski [Brz62] observed that determinizing the reverse of a DFA always gives a minimal DFA for the reversed language. Doing it twice, \(\det(\mathrm{rev}(\det(\mathrm{rev}(A))))\), minimizes \(A\) using nothing but the subset construction. Its worst case is exponential, but it is short, it works directly on NFAs, and it often performs well in practice.

2. Definitions and algorithms¶

Definition 1.4.1 (Nerode equivalence)

For \(L \subseteq \Sigma^{*}\), words \(u, v\) are Nerode-equivalent, \(u \equiv_L v\), if for every \(z \in \Sigma^{*}\), \(uz \in L \iff vz \in L\) (equivalently \(u^{-1}L = v^{-1}L\), Definition 1.3.1). \(\equiv_L\) is an equivalence relation and a right congruence: \(u \equiv_L v \Rightarrow ua \equiv_L va\). Its number of classes is its index.

Definition 1.4.2 (Equivalent states, \(k\)-equivalence)

In a complete DFA \(A = (Q, \Sigma, \delta, q_0, F)\), states \(p, q\) are equivalent, \(p \sim q\), if for every \(z\), \(\hat\delta(p, z) \in F \iff \hat\delta(q, z) \in F\). They are \(k\)-equivalent, \(p \sim_k q\), if this holds for every \(z\) with \(\lvert z \rvert \le k\). A word \(z\) with \(\hat\delta(p,z) \in F \not\iff \hat\delta(q,z) \in F\) distinguishes \(p\) and \(q\). For lexers, replace "\(\in F\)" by "has the same accept tag".

Definition 1.4.3 (Partition, splitter, quotient)

A partition \(P\) of \(Q\) is a set of disjoint nonempty blocks covering \(Q\); \(P'\) refines \(P\) if every block of \(P'\) lies inside a block of \(P\). For a block \(B\) and symbol \(a\), \(\mathrm{pre}_a(B) \triangleq \{\, q \mid \delta(q, a) \in B \,\}\). \((B, a)\) splits a block \(Y\) if \(Y \cap \mathrm{pre}_a(B)\) and \(Y \setminus \mathrm{pre}_a(B)\) are both nonempty. \(P\) is stable if no pair \((B, a)\) with \(B \in P\) splits any block of \(P\). The quotient \(A/P\) has the blocks as states, \(\delta([q], a) = [\delta(q, a)]\), start \([q_0]\), and final blocks those inside \(F\); it is well defined when \(P\) is stable and refines \(\{F, Q \setminus F\}\).

Distinguishing words on the running example

In the DFA A–E of Lesson 1.2, the word bb distinguishes B from A (B \(\xrightarrow{bb}\) E accepts, A \(\xrightarrow{bb}\) C does not); nothing distinguishes A from C: they have the same successors. So A \(\sim\) C, and the Nerode classes of \(L(r_0)\) are the four sets of words "ending in (no useful suffix)", "ending in a", "ending in ab", "ending in abb".

Moore's algorithm¶

Algorithm 1.4.4 (Moore's partition refinement)

Input: a complete DFA \(A\) with \(n\) states over \(k\) symbol classes, all states reachable.
Output: the partition of \(Q\) into \(\sim\)-classes.
Precondition: \(A\) complete (a dead state added if needed) and reachable.
Postcondition: the returned partition is \(Q/\!\sim\) (Theorem 1.4.10); \(A/(Q/\!\sim)\) is the minimal DFA.
Invariant: after round \(i\), the partition is \(Q/\!\sim_i\) (Lemma 1.4.9).

function Moore(A):
    P ← { F, Q ∖ F } without empty blocks      # lexers: one block per accept tag, plus non-final
    loop:
        for q in Q:
            sig(q) ← (block of q in P, block of δ(q, c1) in P, …, block of δ(q, ck) in P)
        P' ← group the states by sig
        if |P'| = |P|: return P                 # no block split: stable
        P ← P'

re2c minimizes with Moore's algorithm (and keeps table filling as a reference)

Reproduce (re2c 3.1; source at tag 3.1; any OS):

re2c --help | grep -A7 -- '--dfa-minimization'
curl -sSfL https://raw.githubusercontent.com/skvadrik/re2c/3.1/src/dfa/minimization.cc -o minimization.cc
sed -n '28,38p' minimization.cc

Output (complete):

    --dfa-minimization <moore | table>

        Internal option: DFA minimization algorithm used by re2c. The moore
        option is the Moore algorithm (it is the default). The table option is
        the "table filling" algorithm. Both algorithms should produce the same
        DFA up to states relabeling; table filling is simpler and much slower
        and serves as a reference implementation.
 * note [DFA minimization: Moore algorithm]
 *
 * The algorithm maintains partition of DFA states.
 * Initial partition is coarse: states are distinguished according
 * to their rule and tag set. Partition is gradually refined: each
 * set of states is split into minimal number of subsets such that
 * for all states in a subset transitions on the same symbol go to
 * the same set of states.
 * The algorithm loops until partition stops changing.
 */

What to notice: the initial partition is "by rule and tag set", the lexer version of \(\{F, Q \setminus F\}\) in Algorithm 1.4.4, and the loop "until partition stops changing" is its termination test. The "table filling" alternative is the pairwise Myhill–Nerode test (\(O(n^{2})\) pairs); the course's oracle uses it the same way, as a cross-check (distinguishable_pairs in tools/course/lib/regex.py).

Hopcroft's algorithm¶

Algorithm 1.4.5 (Hopcroft's algorithm)

Input: a complete, reachable DFA \(A\); \(n = \lvert Q \rvert\), \(k\) symbol classes.
Output: \(Q/\!\sim\).
Precondition: as Algorithm 1.4.4.
Postcondition: \(P = Q/\!\sim\) (Theorem 1.4.12).
Invariant: (I1) \(P\) refines the initial partition and \(\sim\) refines \(P\) (no two equivalent states are ever separated); (I2) every block of the initial partition, and every block created by a split, is either on the worklist with every symbol or is covered by the "difference" argument of Lemma 1.4.11, so that when \(W\) is empty \(P\) is stable.

function Hopcroft(A):
    P ← initial partition (by accept tag)
    W ← { (B, a) | B ∈ P except one largest block, a ∈ classes }
    while W not empty:
        (B, a) ← remove any element of W
        X ← pre_a(B)                             # via inverse transition lists
        for each block Y of P with Y ∩ X ≠ ∅ and Y ∖ X ≠ ∅:
            replace Y in P by Y1 = Y ∩ X and Y2 = Y ∖ X
            for c in classes:
                if (Y, c) ∈ W: replace it by (Y1, c) and (Y2, c)
                else:          add (smaller of Y1, Y2, c) to W
    return P

Blocks are kept as doubly linked lists or as a permutation array with block boundaries, so a split costs \(O(\lvert Y \cap X \rvert)\); pre_a uses precomputed inverse edges.

Hopcroft in Rust's regex-automata: minimized tables are smaller

Reproduce (rustc 1.94.1, cargo 1.94.1, regex-automata 0.4.9 from crates.io):

cargo new --quiet rahop && cd rahop
cargo add -q regex-automata@=0.4.9
cat > src/main.rs <<'EOF'
use regex_automata::dfa::{dense, StartKind};

fn main() {
    for pattern in ["(a|b)*abb", "xy|zy", "(ab|cb)d", "if|for|fi|of"] {
        let mut sizes = vec![];
        for minimize in [false, true] {
            let dfa = dense::Builder::new()
                .configure(dense::Config::new().minimize(minimize).start_kind(StartKind::Anchored))
                .syntax(regex_automata::util::syntax::Config::new().unicode(false))
                .build(pattern)
                .unwrap();
            sizes.push(dfa.memory_usage());
        }
        println!("{:<12} table bytes: determinized {:>4}, minimized {:>4}", pattern, sizes[0], sizes[1]);
    }
}
EOF
cargo run -q
curl -sSfL https://raw.githubusercontent.com/rust-lang/regex/regex-automata-0.4.9/regex-automata/src/dfa/minimize.rs | sed -n '13p'

Output (complete):

(a|b)*abb    table bytes: determinized  376, minimized  376
xy|zy        table bytes: determinized  288, minimized  256
(ab|cb)d     table bytes: determinized  320, minimized  288
if|for|fi|of table bytes: determinized  640, minimized  576
/// An implementation of Hopcroft's algorithm for minimizing DFAs.

What to notice: each removed state saves one table row (32 bytes here: the stride of the byte-class table). xy|zy loses one state: after x and after z the automaton needs the same y (the Nerode classes of x and z coincide). (a|b)*abb does not shrink because regex-automata's determinizer already avoided the A/C duplication this lesson removes by hand. minimize(true) runs the Hopcroft implementation in src/dfa/minimize.rs.

Brzozowski's double reversal¶

Algorithm 1.4.6 (Brzozowski's minimization)

Input: a DFA or NFA \(A\) over symbol classes.
Output: the minimal complete DFA of \(L(A)\).
Precondition: none (works on NFAs too).
Postcondition: the result is minimal (Theorem 1.4.13).
Invariant: after the first Det(Rev(·)), the automaton is deterministic, accessible, and recognizes \(L(A)^{R}\).

function Rev(A):                  # NFA: flip every edge; start set ← F; final set ← {q0}
    edges' ← { (q, a, p) | (p, a, q) edge of A }
    return (Q, Σ, edges', starts = F, finals = {q0})

function Det(N):                  # Algorithm 1.2.5 started from the SET N.starts (no fresh state),
                                  # keeping only reachable subsets; the empty set is the dead state
function Brzozowski(A):
    return Det(Rev(Det(Rev(A))))

Starting the subset construction from the set of old final states matters: a fresh start state with ε-edges to them would create a subset different from every other and break minimality (the course oracle had exactly this bug before its tests caught it; reverse_nfa in tools/course/lib/regex.py explains).

dk.brics.automaton offers all three minimizers

Reproduce (OpenJDK 21.0.10, dk.brics.automaton 1.12-4 from Maven Central; any OS):

curl -sSfL -o brics.jar https://repo1.maven.org/maven2/dk/brics/automaton/1.12-4/automaton-1.12-4.jar
mkdir -p jmin && cat > jmin/Min.java <<'EOF'
import dk.brics.automaton.*;

public class Min {
    public static void main(String[] args) {
        String[] patterns = {"(a|b)*abb", "(a|b)*a(a|b)(a|b)(a|b)(a|b)", "xy|zy", "(if|for|fi|of)"};
        int[] algos = {Automaton.MINIMIZE_HOPCROFT, Automaton.MINIMIZE_BRZOZOWSKI, Automaton.MINIMIZE_HUFFMAN};
        String[] names = {"Hopcroft", "Brzozowski", "Huffman"};
        for (String p : patterns) {
            StringBuilder line = new StringBuilder(String.format("%-30s", p));
            Automaton base = new RegExp(p).toAutomaton(false);   // not minimized yet
            base.determinize();
            line.append(String.format(" determinized=%-3d", base.getNumberOfStates()));
            for (int i = 0; i < algos.length; i++) {
                Automaton.setMinimization(algos[i]);
                Automaton a = new RegExp(p).toAutomaton(false);
                a.minimize();
                line.append(String.format(" %s=%d", names[i], a.getNumberOfStates()));
            }
            System.out.println(line);
        }
    }
}
EOF
javac -cp brics.jar -d jmin jmin/Min.java && java -cp brics.jar:jmin Min

Output (complete):

(a|b)*abb                      determinized=5   Hopcroft=4 Brzozowski=4 Huffman=4
(a|b)*a(a|b)(a|b)(a|b)(a|b)    determinized=33  Hopcroft=32 Brzozowski=32 Huffman=32
xy|zy                          determinized=5   Hopcroft=3 Brzozowski=3 Huffman=3
(if|for|fi|of)                 determinized=9   Hopcroft=5 Brzozowski=5 Huffman=5

What to notice: the library counts states without the dead state. \((a|b)^{*}abb\): five states after determinization (A–E of Lesson 1.2) and four after minimization, with every algorithm, as Theorem 1.4.8 (uniqueness) predicts. \((a|b)^{*}a(a|b)^{4}\) keeps \(2^{5} = 32\) states: minimization cannot beat Proposition 1.2.11. MinimizationOperations.minimizeBrzozowski is literally two calls of determinize(a, reverse(a)), where reverse returns the set of new initial states (commit 582d8f3 of cs-au-dk/dk.brics.automaton, src/dk/brics/automaton/MinimizationOperations.java) [BRICS-Min]. "Huffman" is the table-filling algorithm.

3. Worked example¶

The input is the DFA of Lesson 1.2 §3 (states A–E over \(\{a, b\}\); complete: every transition is defined; E accepting). Every table below was produced with the oracle functions moore, hopcroft and brzozowski_minimize of tools/course/lib/regex.py.

Moore's algorithm¶

Signature of a state in a round = (its block, block of its a-successor, block of its b-successor), blocks named by the previous round:

round	partition	what split and why
0	{A, B, C, D}	initial: non-final / final
1	{A, B, C} {D} {E}	D's `b`-successor E is in the final block; A, B, C go to {A,B,C,D} on `b`
2	{A, C} {B} {D} {E}	B's `b`-successor D is now in its own block; A and C go to C (block {A,B,C})
3	{A, C} {B} {D} {E}	no change: stable

Two refining rounds and one confirming round. The minimal DFA has four states:

state	a	b	accepting
→	B	{A, C}
B	B	D
D	B	E
E	B	{A, C}	yes

Hopcroft's algorithm¶

Initial partition {A, B, C, D} (the largest block, not queued) and {E}; worklist \(W\) = ({E}, a), ({E}, b):

step	splitter	\(\mathrm{pre}\)	splits	worklist after
1	({E}, a)	{}	–	({E}, b)
2	({E}, b)	{D}	{A,B,C,D} → {D} + {A,B,C}	({D}, a) ({D}, b)
3	({D}, a)	{}	–	({D}, b)
4	({D}, b)	{B}	{A,B,C} → {B} + {A,C}	({B}, a) ({B}, b)
5	({B}, a)	{A, B, C, D, E}	none (every block lies inside pre)	({B}, b)
6	({B}, b)	{}	–	(empty)

In step 2, ({A,B,C,D}, ·) was not on the worklist, so only the smaller half {D} was queued; in step 4 likewise {B}. Same final partition as Moore.

Try it

./course drill dfa-minimize --seed 2 --difficulty hard (with an unreachable state to remove first), then --solution for the Moore and Hopcroft traces.

Brzozowski's double reversal¶

First pass, \(\det(\mathrm{rev}(A))\), starting from the set of old final states {E}; a subset is final iff it contains the old start A:

subset	on a	on b	final
→	∅	{D}
{D}	∅	{B}
{B}	{A, B, C, D, E}	∅
{A, B, C, D, E}	{A, B, C, D, E}	{A, B, C, D, E}	yes

(Nothing enters E on a; B is entered on a from every state.) Name these \(S_0, \dots, S_3\). Second pass, \(\det(\mathrm{rev}(\cdot))\) from {S3}; final iff it contains \(S_0\):

subset	on a	on b	final
→	{S2, S3}	{S3}
{S2, S3}	{S2, S3}	{S1, S3}
{S1, S3}	{S2, S3}	{S0, S3}
{S0, S3}	{S2, S3}	{S3}	yes

Four states, isomorphic to the Moore/Hopcroft result under {S3} ↦ {A,C}, {S2,S3} ↦ B, {S1,S3} ↦ D, {S0,S3} ↦ E (Theorem 1.4.8).

4. Invariants and correctness¶

Moore's algorithm¶

Theorem 1.4.7 (Myhill–Nerode)

\(L\) is regular iff \(\equiv_L\) has finite index. In that case the minimal complete DFA for \(L\) has exactly \(\mathrm{index}(\equiv_L)\) states, and \(A_L = (\Sigma^{*}/\!\equiv_L,\ \Sigma,\ \delta([u], a) = [ua],\ [\varepsilon],\ \{[u] \mid u \in L\})\) is such a DFA.

Proof

(⇒) Let \(A\) be a complete DFA for \(L\). If \(\hat\delta(q_0, u) = \hat\delta(q_0, v)\) then \(uz\) and \(vz\) end in the same state for every \(z\), so \(u \equiv_L v\). Hence \(\equiv_L\) has at most \(\lvert Q \rvert\) classes; this also shows every DFA for \(L\) has at least \(\mathrm{index}(\equiv_L)\) states. (⇐) \(A_L\) is well defined because \(\equiv_L\) is a right congruence (\(u \equiv_L v \Rightarrow ua \equiv_L va\): apply the definition with \(z = az'\)), and its final states are well defined because \(u \equiv_L v\) with \(z = \varepsilon\) gives \(u \in L \iff v \in L\). By induction \(\hat\delta([\varepsilon], w) = [w]\), so \(A_L\) accepts \(w\) iff \(w \in L\). It has \(\mathrm{index}(\equiv_L)\) states, matching the lower bound. \(\square\)

Theorem 1.4.8 (Uniqueness of the minimal DFA)

Any two minimal complete DFAs for \(L\) are isomorphic (identical up to renaming states).

Proof

Let \(A\) be minimal with all states reachable (an unreachable state could be deleted). Map each state \(q\) to the class \([u]\) of any \(u\) with \(\hat\delta(q_0, u) = q\). It is well defined: two such words reach the same state, so they are Nerode-equivalent (proof of Theorem 1.4.7). It is surjective onto \(\Sigma^{*}/\!\equiv_L\) because every class has a word, which reaches some state. \(\lvert Q \rvert = \mathrm{index}(\equiv_L)\) by minimality, so it is a bijection. It maps transitions to transitions (\(\hat\delta(q_0, ua) = \delta(q, a) \mapsto [ua] = \delta_L([u], a)\)), the start to \([\varepsilon]\) and final states to final classes. So every minimal DFA is isomorphic to \(A_L\). \(\square\)

Lemma 1.4.9 (Moore's rounds compute \(\sim_i\))

\(p \sim_0 q\) iff \(p, q\) are both final or both non-final (both have the same tag, for lexers), and \(p \sim_{i+1} q\) iff \(p \sim_i q\) and \(\delta(p, a) \sim_i \delta(q, a)\) for every \(a\). Consequently round \(i\) of Algorithm 1.4.4 ends with \(P = Q/\!\sim_i\).

Proof

A word of length \(\le i + 1\) is ε or \(az\) with \(\lvert z \rvert \le i\); ε distinguishes exactly what \(\sim_0\) does, and \(az\) distinguishes \(p, q\) iff \(z\) distinguishes \(\delta(p, a), \delta(q, a)\). That is the recurrence. Round \(i + 1\) groups states by (block under \(\sim_i\), blocks of successors under \(\sim_i\)), which by the recurrence is exactly grouping by \(\sim_{i+1}\); induction on \(i\) starting from the initial partition. \(\square\)

Theorem 1.4.10 (Moore is correct and stops within \(n - 2\) refining rounds)

Algorithm 1.4.4 returns \(Q/\!\sim\) after at most \(\max(0, n - 2)\) rounds that change the partition, plus one confirming round; the quotient is the minimal DFA of \(L(A)\).

Proof

Each refining round increases the number of blocks by at least one, from at least 2 (if both \(F\) and \(Q \setminus F\) are nonempty) to at most \(n\): at most \(n - 2\) refining rounds. If round \(i + 1\) does not change the partition, then \(\sim_{i+1} = \sim_i\), and the recurrence of Lemma 1.4.9 gives \(\sim_{j} = \sim_i\) for all \(j > i\); since \(\sim = \bigcap_j \sim_j\), the result is \(Q/\!\sim\). The partition is stable (equal signatures mean equal successor blocks) and refines \(\{F, Q\setminus F\}\), so the quotient is well defined and recognizes \(L(A)\) (each state behaves like its block). For the reachable \(A\), \(p \sim q\) iff the words reaching \(p\) and \(q\) are Nerode-equivalent, so the blocks are in bijection with the Nerode classes, and the quotient is minimal by Theorem 1.4.7. \(\square\)

Hopcroft's algorithm¶

Lemma 1.4.11 (Hopcroft's invariants)

(I1) Throughout Algorithm 1.4.5, \(\sim\) refines \(P\). (I2) Difference rule: let \(S_1 \subseteq S \subseteq Q\). If no block of a partition \(P\) is split by \((S, a)\) nor by \((S_1, a)\), then none is split by \((S \setminus S_1, a)\). (I3) Refinement rule: if no block of \(P\) is split by \((S, a)\), the same holds for every partition refining \(P\).

Proof

(I1) by induction over the splits. Initially blocks differ only by accept tag, and states with different tags are distinguished by ε. A split puts \(p\) and \(q\) apart only if \(\delta(p, a) \in B\) and \(\delta(q, a) \notin B\) for a current block \(B\); by the induction hypothesis \(\sim\) refines \(P\), so \(\delta(p, a) \not\sim \delta(q, a)\), hence \(p \not\sim q\). (I2) \(\delta(\cdot, a)\) is a function, so \(\mathrm{pre}_a(S \setminus S_1) = \mathrm{pre}_a(S) \setminus \mathrm{pre}_a(S_1)\). A block \(Z\) not split by \((S, a)\) or \((S_1, a)\) lies entirely inside or entirely outside each of \(\mathrm{pre}_a(S)\) and \(\mathrm{pre}_a(S_1)\), hence entirely inside or outside their difference. (I3) A block of a finer partition lies inside a block of \(P\), which lies inside or outside \(\mathrm{pre}_a(S)\). \(\square\)

Theorem 1.4.12 (Hopcroft is correct)

Algorithm 1.4.5 terminates and returns \(Q/\!\sim\).

Proof sketch (full proof: [Knu01, §4]; also [Gri73])

Termination: each iteration removes a pair from \(W\); a pair is added only when a block splits, at most \(n - 1\) times, each adding at most \(2k\) pairs. Stability at the end: call a set \(S\) settled for \(a\) if, from some moment on, no block of \(P\) is ever split by \((S, a)\). By (I3), a set becomes settled for \(a\) as soon as \((S, a)\) is processed. \(Q\) is settled for every \(a\) (every block lies inside \(\mathrm{pre}_a(Q) = Q\)). Consider the tree of blocks: the root \(Q\) has the initial blocks as children, and a split makes \(Y_1, Y_2\) the children of \(Y\). We show every node is eventually settled for every \(a\). For the initial blocks, all but the largest are queued; the largest is \(Q\) minus the others, settled by (I2) applied repeatedly. When \(Y\) splits: if \((Y, a)\) was still queued, both halves are queued; otherwise \(Y\) is settled (it was processed, or it is an ancestor-derived settled set) and the smaller half \(H\) is queued, and then the other half \(Y \setminus H\) is settled by (I2). Hence when \(W\) is empty every block of \(P\) is settled for every symbol: \(P\) is stable. Correctness: a stable partition refining the initial one satisfies, by induction on \(\lvert z \rvert\), "states in one block agree on every word \(z\)", so every block lies inside a \(\sim\)-class; with (I1), \(P = Q/\!\sim\).

Brzozowski's double reversal¶

Theorem 1.4.13 (Brzozowski)

If \(A\) is deterministic and every state is reachable, then \(\det(\mathrm{rev}(A))\) (subset construction started from the set of final states, reachable subsets only, the empty set as dead state) is a minimal complete DFA for \(L(A)^{R}\). Hence \(\det(\mathrm{rev}(\det(\mathrm{rev}(A'))))\) is minimal for \(L(A')\) for any automaton \(A'\).

Proof

Let \(D = \det(\mathrm{rev}(A))\). Its state reached on \(w\) is \(S_w = \{\, q \mid \hat\delta_A(q, w^{R}) \in F \,\}\), the states of \(A\) from which \(w^{R}\) leads to acceptance. \(D\) is deterministic and, by construction, reachable. By Theorem 1.4.7 it is minimal iff no two different states are equivalent, i.e. iff \(S_u \neq S_v\) implies \(u^{-1}L^{R} \neq v^{-1}L^{R}\). Take \(q \in S_u \setminus S_v\) (or symmetrically). \(q\) is reachable in \(A\): \(\hat\delta_A(q_0, x) = q\) for some \(x\). Then \(x\,u^{R} \in L(A)\) (from \(q\), \(u^{R}\) accepts), so \(u\,x^{R} \in L^{R}\); and \(x\,v^{R} \notin L(A)\) because \(A\) is deterministic, so \(x\) leads only to \(q\), and \(q \notin S_v\). Hence \(x^{R} \in u^{-1}L^{R} \setminus v^{-1}L^{R}\). If \(S_u = \emptyset \neq S_v\) the same argument with \(q \in S_v\) applies. The second claim: \(\det(\mathrm{rev}(A'))\) is deterministic, reachable and recognizes \(L(A')^{R}\) (Theorem 1.2.10 applied to the reversed automaton), so the first claim applied to it gives a minimal DFA for \((L(A')^{R})^{R} = L(A')\). \(\square\)

When it breaks: Theorem 1.4.13 needs the input of each \(\det(\mathrm{rev}(\cdot))\) to be deterministic and reachable. Brzozowski's method is not a tag-aware lexer minimizer either: reversal forgets which rule accepted, so the lab falls back to Hopcroft for multi-rule automata (solutions/labs/ch01-regex/src/DFA.cpp, minimize).

5. Complexity¶

Variables: \(n\) = DFA states, \(k\) = symbol classes, \(m\) = states of the input to Brzozowski's method.

Technique	Time (worst)	Time (typical)	Space
Moore	\(O(k n^{2})\): up to \(n-2\) rounds of \(O(kn)\) (hashing signatures)	a few rounds: \(O(kn)\) each	\(O(kn)\)
Hopcroft	\(O(k n \log n)\)	same; larger constant than a Moore round	\(O(kn)\) for inverse edges
Brzozowski	\(O(k\,2^{n})\) intermediate DFA	often fast when the input comes from a subset construction	intermediate DFA
Table filling (reference)	\(O(k n^{2})\) pairs, repeated until stable: \(O(kn^{4})\) naive	–	\(O(n^{2})\)

Proposition 1.4.14 (Moore needs \(n - 2\) refining rounds on a chain)

For \(L_n = \{a^{n-2}\}\) (over bytes: classes a and "other"), the minimal complete DFA has \(n\) states (a chain \(0 \to 1 \to \cdots \to n-2\), final \(n-2\), plus a dead state) and Moore's algorithm makes exactly \(n - 2\) refining rounds.

Proof

Round 0 separates \(\{n-2\}\) from the rest. By induction, after round \(i \ge 1\) the blocks are \(\{n-2\}, \{n-3\}, \dots, \{n-2-i\}\) (singletons) and one block containing the states \(0, \dots, n-3-i\) and the dead state: round \(i+1\) separates exactly \(n - 3 - i\), the only remaining state whose a-successor (\(n-2-i\)) was separated in round \(i\). The dead state is separated from state \(0\) only in the last round, \(i = n - 2\) (for \(n \ge 3\)), when state 0's successor 1 becomes a singleton. So there are \(n - 2\) refining rounds, and \(\Theta(n^{2})\) total work. The oracle confirms \(n - 2\) for \(n = 3, \dots, 8\). \(\square\)

Proposition 1.4.15 (Hopcroft is \(O(kn \log n)\))

With the smaller-half rule and \(O(\lvert Y \cap X\rvert)\) splitting, Algorithm 1.4.5 runs in \(O(kn\log n)\) time.

Proof sketch (full proof: [Knu01, §5]; [Hop71])

Charge the cost of processing \((B, a)\), which is \(O(\lvert \mathrm{pre}_a(B) \rvert)\) plus splitting cost of the same order, to the edges \((p, a, q)\) with \(q \in B\). Fix a state \(q\) and a symbol \(a\), and look at the pairs \((B, a)\) with \(q \in B\) that are ever on \(W\). When a queued \((Y, a)\) is replaced by \((Y_1, a)\) and \((Y_2, a)\), \(q\) still lies in exactly one queued pair, so replacement never adds a pair for \(q\). A new pair for \(q\) appears only when \((Y, a)\) is not queued and \(q\) lies in the smaller half, of size at most \(\lvert Y \rvert / 2\); and \(Y\) is contained in the block of the previous pair containing \(q\) (blocks only shrink). So the sizes of the successive processed pairs containing \(q\) at least halve: \(q\) is in at most \(\log_2 n + 1\) processed splitters per symbol, and each edge into \(q\) is charged \(O(\log n)\) times. Summing over the \(kn\) edges gives \(O(kn \log n)\). The bound needs the worklist of (block, symbol) pairs used here (Gries's formulation); Knuutila shows that Hopcroft's original, which queues blocks, is not \(O(kn\log n)\) when \(k\) is not fixed [Knu01].

Proposition 1.4.16 (Brzozowski's intermediate DFA can be exponential)

Let \(B_k\) be the minimal DFA of \(L_k^{R}\) = "the \(k\)-th symbol from the start is \(a\)" (\(k + 2\) states). Brzozowski's method applied to \(B_k\) builds, in its first pass, a DFA for \(L_k\), which has at least \(2^{k}\) states (Proposition 1.2.11), although the input and the output have \(k + 2\) states.

Proof

The first pass computes \(\det(\mathrm{rev}(B_k))\), a DFA for \(L(B_k)^{R} = L_k\); by Proposition 1.2.11 every DFA for \(L_k\) has at least \(2^{k}\) states, and by Theorem 1.4.13 this one is exactly minimal for \(L_k\). The second pass returns the minimal DFA of \(L_k^{R}\), which has \(k + 2\) states. \(\square\)

At scale. In the lab (ch01-regexbench, section 3), minimizing the \(2^{k+1}+1\)-state DFAs of \((a|b)^{*}a(a|b)^{k}\) takes, for \(k = 12\) (8193 states), 25 ms with Hopcroft, 36 ms with Moore and 30 ms with Brzozowski (the figures of the chapter README; they vary by about 1.5× between runs) (whose first pass is small here, the reverse language being easy). Lexer DFAs are tiny by comparison: Pebble's subset-constructed lexer DFA (147 live states) minimizes to 135 states, dead state included, in well under a millisecond.

Moore's algorithm¶

Table filling (Huffman; the "Myhill–Nerode table", [HMU07 §4.4]): mark distinguishable pairs until nothing changes; \(O(n^{2})\) memory, easy to prove, used as a reference (re2c, the course oracle).
Signature hashing (the lab's DFA.cpp, re2c): each round is a sort or hash of \((\text{block}, \text{successor blocks})\) vectors; fast when few rounds are needed, which is typical for lexer DFAs.

Hopcroft's algorithm¶

Valmari–Lehtinen / "partition refinement with the marking trick": the same bound with simpler data structures; widely used in model checkers.
Incremental and acyclic variants: for acyclic DFAs (keyword sets, dictionaries) a single bottom-up pass merging states with equal signatures is linear (Revuz's algorithm); tries of keywords (Lesson 1.8) minimize this way.

Brzozowski's double reversal¶

Works on NFAs directly: no separate determinization of the input is needed, since the second pass determinizes anyway.
Hybrid: run one reversal-determinization to get a small DFA for \(L^R\), then Hopcroft, when the reversed language is known to be well behaved.

7. In real compilers¶

Moore's algorithm¶

re2c src/dfa/minimization.cc — minimization_moore (default) and minimization_table (reference), re2c 3.1 [RE2C-Min]; box in §2.
The course lab solutions/labs/ch01-regex/src/DFA.cpp — moore.

Hopcroft's algorithm¶

Rust regex-automata src/dfa/minimize.rs — Minimizer::run ("basically Hopcroft's algorithm"), regex-automata 0.4.9 [REGEX-AUTOMATA-Min]; box in §2.
dk.brics.automaton MinimizationOperations.minimizeHopcroft [BRICS-Min].
flex has no minimization pass; its DFAs come straight from the subset construction (Lesson 1.2 §2 box).

Find where LLVM does it. LLVM has no general DFA minimizer, but TableGen's DFAPacketizer backend builds automata for VLIW packetization. Open llvm/utils/TableGen/DFAEmitter.cpp at llvmorg-23.1.2 and find how states are deduplicated during construction. Question: does it minimize after building, or intern states by content while determinizing? (Quiz llvm-dfa-emitter.)

Brzozowski's double reversal¶

dk.brics.automaton MinimizationOperations.minimizeBrzozowski — two determinize(a, reverse(a)) calls [BRICS-Min]; box in §2.
The course lab and oracle: determinizeReverse in solutions/labs/ch01-regex/src/DFA.cpp, brzozowski_minimize in tools/course/lib/regex.py.

8. Comparison¶

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
Moore	exact minimum (Theorem 1.4.10); tag-aware	\(O(kn^{2})\) worst, few rounds in practice	partition per round (easy to debug)	small	re2c default, quick tools
Hopcroft	exact minimum; tag-aware	\(O(kn\log n)\) worst	–	moderate (worklist, block lists)	automata libraries, `regex-automata`, the lab's default
Brzozowski	exact minimum; works on NFAs; not tag-aware	\(O(k\,2^{n})\) worst intermediate	–	tiny if you have a subset construction	libraries (dk.brics), teaching, NFA inputs

Choose Moore when the DFA is small or you want the simplest correct code. Choose Hopcroft when DFAs can be large and you need a guaranteed bound. Choose Brzozowski when you already have a subset construction and a reversal, the input is an NFA, and tags do not matter.

9. Assessment¶

Technique	Quiz ids	Drill	Flashcard tag	Exercises
Moore's algorithm	`moore-rounds`, `myhill-nerode-classes`	`./course drill dfa-minimize --difficulty medium` (asks the number of rounds)	`moore`	Lab L5 (★ Moore)
Hopcroft's algorithm	`hopcroft-smaller-half`, `myhill-nerode-classes`	`./course drill dfa-minimize` (`--solution` traces Hopcroft)	`hopcroft`	Lab L5
Brzozowski's double reversal	`brzozowski-reachable`, `llvm-dfa-emitter`	`./course drill dfa-minimize --difficulty hard` (compare with a hand double reversal)	`brzozowski-minimization`	Lab L5 (★ Brzozowski)

Pitfall

Minimize the complete DFA and remove unreachable states first. An unreachable state is never merged away by partition refinement (it may be equivalent to nothing), and a missing dead state makes two states look equivalent when one of them would reject by falling off the table.

References¶

See the chapter references.

Lesson 1.4 — DFA minimization and the Myhill–Nerode theorem¶

1. Problem and motivation¶

Moore's algorithm¶

Hopcroft's algorithm¶

Brzozowski's double reversal¶

2. Definitions and algorithms¶

Moore's algorithm¶

Hopcroft's algorithm¶

Brzozowski's double reversal¶

3. Worked example¶

Moore's algorithm¶

Hopcroft's algorithm¶

Brzozowski's double reversal¶

4. Invariants and correctness¶

Moore's algorithm¶

Hopcroft's algorithm¶

Brzozowski's double reversal¶

5. Complexity¶

6. Variants and refinements¶

Moore's algorithm¶

Hopcroft's algorithm¶

Brzozowski's double reversal¶

7. In real compilers¶

Moore's algorithm¶

Hopcroft's algorithm¶

Brzozowski's double reversal¶

8. Comparison¶

9. Assessment¶

References¶