TWO STATES ARE EQUIVALENT IF NO INPUT STRING CAN TELL THEM APART. FORMALLY: states p and q are EQUIVALENT (written p ≡ q) if for EVERY string w ∈ Σ*, δ̂(p, w) ∈ F ⟺ δ̂(q, w) ∈ F — starting from p and from q, the same strings are accepted. If some string w leads one to an accepting state and the other to a non-accepting state, that w DISTINGUISHES them. THE k-EQUIVALENCE HIERARCHY, which is what the algorithm actually computes: p ≡₀ q if p and q are both accepting or both non-accepting p ≡ₖ q if no string of length ≤ k distinguishes them THE SEQUENCE STABILISES: once ≡ₖ = ≡ₖ₊₁, no further refinement can occur, and that relation is ≡. With n states this happens within n−1 rounds, so the algorithm always terminates. ── WHY MINIMIZATION IS WELL DEFINED ──────────────────────── THE MYHILL-NERODE THEOREM underwrites the whole topic: A language L is regular if and only if the relation x ≡_L y ⟺ ∀z: (xz ∈ L ⟺ yz ∈ L) has FINITELY MANY equivalence classes; and the number of classes is EXACTLY the number of states in the minimal DFA. TWO CONSEQUENCES WORTH STATING: 1. THE MINIMAL DFA IS UNIQUE UP TO RENAMING OF STATES. This is unusual and powerful — most computational models have no canonical smallest form, but DFAs do. 2. IT GIVES A METHOD FOR PROVING NON-REGULARITY: exhibit infinitely many pairwise distinguishable strings, and the language cannot be regular. For {aⁿbⁿ}, the strings a, aa, aaa, … are pairwise distinguishable (aⁱ and aʲ are separated by bⁱ), so infinitely many classes exist and no DFA can have them all. ── THE TABLE-FILLING ALGORITHM (MOORE'S ALGORITHM) ───────── THE STANDARD EXAM METHOD. STEP 1 — REMOVE UNREACHABLE STATES. Any state not reachable from the start state contributes nothing and is deleted first. THIS STEP IS ROUTINELY FORGOTTEN AND COSTS MARKS. STEP 2 — Draw a table with one cell for each unordered pair of states. STEP 3 — MARK every pair (p,q) where exactly one of p, q is accepting. These are distinguished by ε, the empty string. STEP 4 — REPEAT until no change: for each unmarked pair (p,q) and each symbol a, if the pair (δ(p,a), δ(q,a)) is MARKED, then mark (p,q). STEP 5 — Every pair still UNMARKED is a pair of EQUIVALENT states. Merge each equivalence class into one state. THE LOGIC OF STEP 4: if some string w distinguishes the successors, then the string aw distinguishes p and q — because reading a takes them to the successors, after which w separates them. ── A FULLY WORKED MINIMIZATION ───────────────────────────── DFA with states A, B, C, D, E; alphabet {0,1}; start A; accepting {D}: STATE 0 1 ───────────────── →A B C B B D C B C D B E E B C ───────────────── ROUND 0 — mark pairs differing in acceptance. Only D accepts: MARKED: (A,D), (B,D), (C,D), (D,E) ROUND 1 — examine each unmarked pair: (A,B): on 1 → (C,D), which is MARKED → MARK (A,B) (A,C): on 0 → (B,B) same; on 1 → (C,C) same → leave (A,E): on 0 → (B,B); on 1 → (C,C) → leave (B,C): on 1 → (D,C), MARKED → MARK (B,C) (B,E): on 1 → (D,C), MARKED → MARK (B,E) (C,E): on 0 → (B,B); on 1 → (C,C) → leave ROUND 2 — no further changes. STOP. UNMARKED PAIRS: (A,C), (A,E), (C,E) These form ONE equivalence class {A, C, E}. THE PARTITION IS: { A, C, E }, { B }, { D } VERIFY BY INSPECTION — A, C and E behave identically: A: on 0 → B, on 1 → C C: on 0 → B, on 1 → C E: on 0 → B, on 1 → C Identical successors, so no string can separate them. THE MINIMAL DFA, writing the merged class as P: STATE 0 1 ───────────────── →P B P B B D D B P ───────────────── accepting: D FIVE STATES REDUCED TO THREE. The language, incidentally, is "binary strings ending in 01", and three states is exactly what that needs — one for each amount of progress toward the pattern: P no 0 pending at the end (nothing useful seen yet) B the last symbol was a 0, so a 1 now completes "01" D "01" has just been completed → ACCEPT THIS IS THE MINIMIZATION RESULT MADE CONCRETE: the original five states carried the same three pieces of information between them, with A, C and E all meaning "no 0 pending".

── THE PARTITION REFINEMENT VIEW ─────────────────────────── The same computation seen top-down rather than pair-by-pair, and it is faster to execute by hand on larger machines: START with the partition { non-accepting states }, { accepting states }. REPEAT: split any block whose members send different symbols into different blocks. STOP when no block splits. ON THE SAME EXAMPLE: P₀ = { A, B, C, E } , { D } Refine: on 1, B goes to D (block 2) while A, C, E go to C (block 1). So B separates. P₁ = { A, C, E } , { B } , { D } Refine again: A, C, E all go to B on 0 and to block {A,C,E} on 1 — no split. P₂ = P₁, so STOP. THREE BLOCKS = THREE STATES, agreeing with the table method. HOPCROFT'S ALGORITHM is the refined version, running in O(n log n) rather than the O(n²) of naive table filling — the asymptotically best known, and what production tools use. ── WHY MINIMIZE ──────────────────────────────────────────── 1. HARDWARE COST. n states need ⌈log₂ n⌉ flip-flops. 5 states → ⌈log₂ 5⌉ = 3 flip-flops 3 states → ⌈log₂ 3⌉ = 2 flip-flops A saving of one flip-flop per instance, plus the combinational logic driving it. 2. MEMORY AND SPEED. A smaller transition table fits in cache; for a lexer run over megabytes of source, that is a measurable difference. 3. EQUIVALENCE TESTING — the most theoretically important use. TO DECIDE WHETHER TWO DFAs ACCEPT THE SAME LANGUAGE, MINIMIZE BOTH AND CHECK WHETHER THE RESULTS ARE ISOMORPHIC. Because the minimal DFA is UNIQUE, this is a complete decision procedure — and it is the reason the uniqueness result matters rather than being a curiosity. 4. VERIFICATION. Protocol and circuit equivalence checking reduces to exactly this. 5. UNDERSTANDING. The minimal machine reveals what the language actually requires the machine to remember, with all redundancy stripped away. ── THE COMMON MISTAKES ───────────────────────────────────── · FORGETTING TO REMOVE UNREACHABLE STATES FIRST. The algorithm will happily merge unreachable states with others and give a machine that is correct but not minimal — or leave them in place entirely. · Assuming that states with the same OUTGOING SYMBOLS are equivalent. Equivalence is about WHERE the transitions lead, over all future strings, not about which symbols are accepted. · Forgetting that a DFA must be COMPLETE. If the given machine has missing transitions, add a DEAD (trap) state with all transitions to itself before minimizing — otherwise δ is not a total function and the algorithm's assumptions fail. · Merging an accepting with a non-accepting state. They are distinguished by ε and are marked in round 0; if this happens, the marking was done wrongly. ── THE PLACE OF THIS RESULT ──────────────────────────────── Combining this topic with the previous one gives a complete computational picture of regular languages: REGULAR EXPRESSION ↓ (Thompson's construction) ε-NFA ↓ (subset construction) DFA ↓ (minimization) MINIMAL DFA ← UNIQUE, and a CANONICAL FORM for the language EVERY REGULAR LANGUAGE HAS A UNIQUE CANONICAL REPRESENTATIVE THAT CAN BE COMPUTED MECHANICALLY. That is why questions about regular languages — equivalence, emptiness, finiteness — are all DECIDABLE, in sharp contrast to the same questions for context-free languages and Turing machines later in this section.