Minimizing a DFA

Two DFA states are equivalent if, for every possible remaining input suffix, one leads to acceptance exactly when the other does — no string run from this point on can ever tell them apart. Equivalent states are redundant: merging them produces a smaller machine that still decides exactly the same language.

An unminimized example

This 3-state DFA accepts binary strings ending in 0. Watch what q1 and q2 actually do: both are accept states, and on a 1 both go straight back to q0. They only look different on a 0 — q1 moves to q2, while q2 loops to itself — but since q1 and q2 behave identically from here on, that difference is invisible to any future input.

q0⊢q0⊢q1⊢∈ F

Finding equivalent states

The standard algorithm (table-filling / partition refinement) starts by splitting states into two groups — accepting and non-accepting — since those are trivially distinguishable (the empty suffix alone tells them apart). Then it repeatedly checks: do any two states in the same group go to different groups on some symbol? If so, split them apart. Repeat until no more splits happen.

Here, {q1, q2} start in the same group (both accepting). On 0: q1 → q2 (accepting group), q2 → q2 (accepting group) — same group, no split needed. On 1: both go to q0 (non-accepting group) — same group again. q1 and q2 never diverge, so they merge into one state.

The minimized result

Merging q1 and q2 collapses the machine to two states — provably the fewest possible for this language, since a DFA for "ends in 0" has to distinguish at least "just saw a 0" from "didn't."

q0⊢q0⊢q1⊢∈ F

Your turn