DFA Equivalence Minimization

Merge states only when no future suffix can distinguish their accepted languages. Minimizing a Deterministic Finite Automaton (DFA) identifies and merges equivalent states to produce the smallest possible automaton recognizing the same language. Two states are equivalent if and only if for every possible input string, starting from either state leads to an accepting state or both lead to a rejecting state. The minimization algorithm starts by eliminating unreachable states. Then it partitions the states into blocks of equivalent states.

Experiment

You can experiment with different automaton configurations to observe the minimization process in the DFA Equivalence Minimization module.

1. Select a preset from the Automaton dropdown, such as "Redundant parity" or "Modulo three with trap".
2. Choose a word from the Word dropdown to trace through both the original and minimized automatons.
3. Observe the resulting equivalence blocks and verify that both machines accept or reject the word consistently.