HOPCROFT MINIMIZATION merge states no string can tell apart
Two DFA states are equivalent if no input string, starting from either, ever leads to a different accept/reject outcome. The minimal DFA merges all such states into one. Start by splitting accepting from non-accepting, then refine: a class splits whenever a symbol sends its members to different classes. When nothing splits further, each class is one state of the unique smallest DFA. Hopcroft’s 1971 refinement does it in n log n.
THE TECHNIQUE partition refinement to a fixpoint
A 3-state DFA where states A and B are secretly the same: both non-accepting, both sending 0→B and 1→C. No string distinguishes them, so they merge — 3 states become 2. Watch the distinguishability table fill: live demo
HISTORY & CREDIT Hopcroft 1971; Moore/Huffman earlier
“Hopcroft invented DFA minimisation.” — no. Moore (1956) and Huffman gave the quadratic table-filling method years earlier; Hopcroft’s 1971 contribution is the n log n refinement — faster, not first. The minimal DFA is unique (Myhill-Nerode), whichever algorithm finds it. cited
1956 · Edward Moore (and Huffman) — the table-filling / distinguishability method, O(n²). 1958 · Myhill & Nerode — the theorem: a language’s minimal DFA is unique, its states the equivalence classes of the right-congruence. 1971 · John Hopcroft — “An n log n algorithm for minimizing states in a finite automaton”: partition refinement, always splitting by the smaller half.
Uniqueness is what makes it powerful: two regexes denote the same language iff their minimal DFAs are identical — so minimisation is a decision procedure for regex equivalence. Hopcroft 1971 / Moore 1956
RECOMMEND FOR I-13 the merge, computed
The distinguishability check runs on the canonical compiler — A and B share accept status and targets, so they merge:
$ i13 run hopcroft.i13 # 3-state DFA; A,B non-accepting with identical transitions
d_AB = 0 -- A,B not distinguished by accept status
same_targets = 1 -- on 0 both -> B, on 1 both -> C
minimal_states = 2 -- A and B merge; 3 states collapse to 2
Recommend: Hopcroft minimisation is LIT on I-13 — verified a 3-state DFA collapses to 2 because states A and B share accept status and identical transition targets, computed by the distinguishability check over transition arrays. For an I-13 regex engine (built from Glushkov 176 or Brzozowski 177), this is the pass that yields the unique smallest automaton — and therefore a decision procedure for “do these two patterns match the same strings?” (equal minimal DFAs). Partition-refinement is array bookkeeping; the O(n log n) split-the-smaller-half trick is the optimisation once it scales.