Find the Smallest Equivalent DFA
This tool minimizes a DFA to find the smallest equivalent automaton that recognizes the same language.
Why Minimize DFAs?
Minimizing DFAs has several benefits:
- Reduces the number of states, making the automaton more efficient
- Simplifies the automaton, making it easier to understand and implement
- Provides a canonical representation of the language (up to isomorphism)
The minimization algorithm works by identifying and merging equivalent states - states that have the same behavior for all possible input strings.
Original DFA
Define the DFA you want to minimize
States
| Name | Start | Accept | Actions |
|---|---|---|---|
| q₀ | |||
| q₁ | |||
| q₂ | |||
| q₃ | |||
| q₄ |
Transitions
| From | Symbol(s) | To | Actions |
|---|---|---|---|
| q₀ | a | q₁ | |
| q₀ | b | q₃ | |
| q₁ | a | q₂ | |
| q₁ | b | q₃ | |
| q₂ | a | q₂ | |
| q₂ | b | q₃ | |
| q₃ | a | q₄ | |
| q₃ | b | q₀ | |
| q₄ | a | q₂ | |
| q₄ | b | q₀ |
Preview
Predefined Examples
Choose from these example DFAs to see the minimization process