DFA minimization

Summary

DFA minimization is the task of turning a deterministic finite automaton into an equivalent one with as few states as possible. For every regular language the minimal DFA is unique up to renaming of states, by the Myhill–Nerode theorem. It is computed by removing unreachable states and merging states that no input word can distinguish. Minimal DFAs give a canonical form, so two regular languages are equal exactly when their minimal DFAs are the same up to renaming.