DFA Minimization

Two states of a DFA are equivalent when no string leads from one to an accept state and from the other to a reject state. Merging equivalent states yields the unique (up to renaming) minimal DFA for the language: fewest states among all DFAs for that language. The skills are running the table-filling (distinguishability) algorithm, reading the minimized diagram, and using Myhill-Nerode to prove a lower bound on the number of states.

States $p$ and $q$ are distinguishable if there exists a string $z$ such that exactly one of $\hat{\delta}(p,z)$ and $\hat{\delta}(q,z)$ is accepting. Otherwise they are equivalent (indistinguishable).

Base case: if exactly one of $p,q$ is accepting, they are distinguished by $\varepsilon$.

Inductive step: if for some symbol $a$, the states $\delta(p,a)$ and $\delta(q,a)$ are already distinguishable, then $p$ and $q$ are distinguishable (prepend $a$ to the distinguishing continuation).

For states ordered $q_1,\ldots,q_n$, maintain a triangular table of pairs $\{q_i,q_j\}$ with $i>j$.

The result is the minimal DFA. Hopcroft's algorithm computes the same partition faster ($O(|\Sigma|n\lg n)$ time) but table-filling is the easier one to run by hand.

For a language $L \subseteq \Sigma^*$, define $x \equiv_L y$ iff for every $z \in \Sigma^*$, $xz \in L \Leftrightarrow yz \in L$. This is an equivalence relation, and it is right-invariant: $x \equiv_L y$ implies $xa \equiv_L ya$.

Myhill-Nerode theorem. The following are equivalent: (1) $L$ is regular; (2) $\equiv_L$ has finitely many classes (finite index); (3) $L$ is a union of classes of some right-invariant equivalence of finite index. Moreover, the number of classes of $\equiv_L$ equals the number of states of the minimal complete DFA for $L$, and the minimal DFA is unique up to renaming of states.

Consequences used in exams:

Alphabet $\{a\}$. States $E$ (start, accept), $O$ (reject), $E_2$ (accept) with transitions $E \xrightarrow{a} O$, $O \xrightarrow{a} E_2$, $E_2 \xrightarrow{a} O$. States $E$ and $E_2$ are both accepting and move to $O$ on $a$; $O$ is rejecting. Table marks $(E,O)$ and $(E_2,O)$ immediately; $(E,E_2)$ never marks. Merge $\{E,E_2\}$ into one accept state. Minimal DFA has 2 states.

DFA for strings ending with 0: states $A$ (start), $B$ (accept); $A\xrightarrow{0}B$, $A\xrightarrow{1}A$, $B\xrightarrow{0}B$, $B\xrightarrow{1}A$. Pair $(A,B)$ marked by $\varepsilon$. Minimal already: 2 states.

Time $O(|\Sigma|n^3)$ worst-case for this repeated-scan loop, where $n=|Q|$: there are $O(n)$ propagation rounds and $O(|\Sigma|n^2)$ work per round. A dependency/worklist implementation can achieve $O(|\Sigma|n^2)$.

Any two minimal DFAs for the same language are isomorphic: the Myhill-Nerode classes determine both. Minimization finds that canonical machine.

Marked pairs are exactly the distinguishable ones: soundness by induction on the length of a shortest distinguishing string; completeness because if $p \not\equiv q$, a shortest distinguisher of length $k$ forces a mark after $k$ rounds.

As above: three-state even-$a$ machine minimizes to two states. Distinguishing string for $E$ vs $O$ is $\varepsilon$; for $E$ vs $E_2$ none exists.

Language $L = \{ w \in \{0,1\}^* \mid |w| \equiv 0 \pmod 3 \}$. Strings $\varepsilon, 0, 00$ are pairwise distinguishable:

Hence every DFA needs at least 3 states; the standard mod-3 length DFA meets the bound.

The 4-state progress DFA of the DFA note is not minimal. Its states $\varepsilon$ and 1 are equivalent: both are rejecting, and both go to 0 on 0 and to 1 on 1, so the pair is never marked. The other pairs are marked: 01 against any other state by $\varepsilon$, then 0 against $\varepsilon$ and against 1 because on input 1 they go to the marked pairs (01, 1). Minimal size is 3, matching the three Myhill-Nerode classes listed above.

States A (start), B, C (accept), D (accept). Alphabet {0,1}. Transitions:

First mark pairs mixing accept and reject: (A,C), (A,D), (B,C), (B,D). Unmarked: (A,B), (C,D).

Check (A,B): on 0 go to (B,A) unmarked; on 1 go to (A,C) which is marked. So mark (A,B).

Check (C,D): on 0 go to (D,C) unmarked; on 1 go to (A,A) same state. No mark from this round. Next round still no new marks from (C,D). So C and D merge.

Quotient: states {A}, {B}, {C,D}. The only merge is between the two accept states.

States $A$ (start) to $F$, accepting $\{B, E\}$:

Two states are $k$-equivalent if no string of length at most $k$ distinguishes them. Refine until a round changes nothing.

The minimal DFA has 4 states, $\{A,C,F\}$ becoming the start state. Note that $B$ and $E$ are 1-equivalent but not 2-equivalent. A distinguishing string of length 2 is 01: $B \xrightarrow{0} D \xrightarrow{1} D$ rejects, while $E \xrightarrow{0} F \xrightarrow{1} E$ accepts. (The string 00 does not work: it leads from $B$ to $E$ and from $E$ to $B$, both accepting.)

Table filling and partition refinement agree. Both compute the Myhill-Nerode partition of the reachable states; table filling marks pairs, refinement splits blocks. Refinement is faster to write for 6 or more states.

Add a state E with self-loops that is never reached from A. Table-filling might still compare E to others, but MINIMIZE first deletes E by reachability DFS/BFS from the start. The minimal DFA never includes unreachable states. Always remove them before reporting the state count.

Common misconceptions.