A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
A minimal DFA has the fewest states among all DFAs recognizing the same language. The Hopcroft-Karp algorithm minimizes a DFA in O(n log n) time by repeatedly refining partitions of states based on their distinguishability. Minimization is unique up to isomorphism, making it useful for comparing DFAs.
From the NFA-to-DFA subset construction, you know that converting an NFA can produce a DFA with exponentially many states — many of which may be redundant. Two states are redundant if they behave identically: for every possible input string, both states lead to the same accept/reject outcome. The goal of DFA minimization is to merge all such redundant states, producing the smallest DFA that recognizes the same language.
The core concept is distinguishability. Two states p and q are distinguishable if there exists some string w such that exactly one of δ(p, w) and δ(q, w) is an accepting state — the automaton's behavior starting from p differs from its behavior starting from q for at least one input. States that are *not* distinguishable by any string are called equivalent, and they can be merged into a single state without changing the language. The minimization algorithm works by iteratively finding all distinguishable pairs. Initially, every accept state is distinguishable from every reject state (the empty string distinguishes them). Then, for each pair of states (p, q) not yet marked as distinguishable, the algorithm checks: does some input symbol a send p and q to states that are already known to be distinguishable? If so, p and q are distinguishable too. This process repeats until no new pairs can be marked. The unmarked pairs are equivalent and get merged.
The Hopcroft algorithm refines this idea into an efficient partition refinement procedure. Start with two groups: accept states and non-accept states. Then repeatedly split groups: if the states in a group disagree on where some input symbol sends them (some go to group A, others to group B), split the group accordingly. When no group can be split further, each group becomes a single state in the minimal DFA. The result runs in O(n log n) time, making it practical even for large automata.
A remarkable property of minimal DFAs is uniqueness: for any regular language, there is exactly one minimal DFA (up to renaming of states). This means you can test whether two DFAs recognize the same language by minimizing both and checking if the results are isomorphic — same structure, just different state labels. No other computational model at the regular-language level offers such a clean canonical form. This uniqueness also provides a lower bound: if a language's minimal DFA has k states, then *no* DFA for that language can do better, which connects to the Myhill-Nerode theorem and formal techniques for proving languages are not regular.