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.

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

Worked Example

Consider the Redundant parity automaton. We will trace the state equivalence refinement algorithm. The algorithm initially separates accepting and non-accepting states and then refines these blocks.

Initial states: 0, 1, 2, 3
Transition Table: 0: on0 → 2, on1 → 1; 1: on0 → 3, on1 → 0; 2: on0 → 0, on1 → 3; 3: on0 → 1, on1 → 2
Accepting states: 1, 3
Initial partition (Accept / Reject): Block 1: {1, 3}, Block 2: {0, 2}
Check transitions from Block 2 {0, 2}: 0 on0 → 2 (in Block 2), 0 on1 → 1 (in Block 1); 2 on0 → 0 (in Block 2), 2 on1 → 3 (in Block 1). Both states in Block 2 transition to the same blocks. No split.
Check transitions from Block 1 {1, 3}: 1 on0 → 3 (in Block 1), 1 on1 → 0 (in Block 2); 3 on0 → 1 (in Block 1), 3 on1 → 2 (in Block 2). Both states in Block 1 transition to the same blocks. No split.
Final equivalence blocks: 0, 2 and 1, 3

The algorithm finishes with exactly 2 equivalence classes because all states within each block share identical transition signatures for the input alphabet.

Result exact output minimum states: 2

Limitations

This demonstration operates on finite state machines with binary alphabets (0 and 1) and a predefined maximum state count to keep visualizations accessible. It assumes deterministic transitions and no epsilon-moves. Large DFAs might require optimizations like Hopcroft's algorithm to be minimized efficiently, whereas this interactive visualizer focuses on educational tracing for a small number of states.

References

For more information on the refinement process and formal definitions of language equivalence, see standard textbooks on automata theory and formal languages.

DFA Minimization (Cornell CS2800 Handout)

DFA Equivalence Minimization