Developer tool
DFA Minimizer
Minimize a deterministic finite automaton with Hopcroft's algorithm. Build your DFA in an editable table and see the smallest equivalent machine.
| State | Start | Accept | a | b |
|---|---|---|---|---|
| q0 | ||||
| q1 | ||||
| q2 | ||||
| q3 |
Type one target state number in each cell. A DFA allows a single move per symbol, so “2” is valid and “0, 2” is not. Leave a cell empty for no transition.
Your DFAInput
The deterministic automaton defined in the table above.
start stateaccepting state
Minimized DFAHopcroft's algorithm
Indistinguishable states merged into the smallest DFA for the same language.
| State | a | b |
|---|---|---|
| M0{q0} | M1 | — |
| M1{q1} | M2 | M2 |
| M2{q2,q3} | — | — |
start stateaccepting state
Type a string to trace it through the automaton. The empty string is allowed.
About this tool
Minimize a DFA with Hopcroft's algorithm
DFA minimization is the final stage of a lexical analyzer generator. Two states are equivalent when no string can distinguish them, so they can be merged without changing the language. Hopcroft's algorithm computes these equivalence classes by partition refinement: it begins by separating accepting from non-accepting states, then repeatedly splits any block whose members transition into different blocks on some symbol, using a worklist of splitters to do this in near-linear time. The blocks that remain are the states of the minimal DFA.
Enter your DFA in the transition table and the tool minimizes it live. It shows your input DFA as a diagram, the minimized DFA as a diagram and transition table with each new state labeled by the original states it merged, and a string tester so you can confirm the smaller machine accepts the same language. Unreachable states and dead trap states are dropped automatically.
How it works
Minimize a DFA in three steps
- 1Define the DFA
Set the alphabet and states, pick the start and accepting states, and click one target per cell.
- 2Read the minimal DFA
See the merged automaton as a diagram and table, with each state labeled by the states it combined.
- 3Test a string
Type an input to trace it through the minimized DFA and confirm acceptance.
Common questions
Hopcroft's algorithm FAQ
What does DFA minimization do?
Minimization finds the DFA with the fewest possible states that accepts exactly the same language. It works by merging states that are indistinguishable, meaning no input string can ever lead one to acceptance and the other to rejection.
How does Hopcroft's algorithm work?
Hopcroft's algorithm starts with two groups, the accepting and the non-accepting states, then repeatedly splits any group whose members behave differently: if a symbol sends some members into one group and the rest into another, the group is divided. It uses a worklist of splitters to reach the coarsest stable partition efficiently. Each final group becomes one state of the minimal DFA.
How do I enter my DFA?
Use the editable transition table. Set the alphabet, add states, choose the start and accepting states, then click one target number per cell to set that symbol's move. Because it is a DFA, each cell allows only a single target; click it again to clear it.
What happens to unreachable or dead states?
States that cannot be reached from the start state, and trap states from which acceptance is impossible, are removed during minimization. That is expected: they carry no information about the language, so the minimal DFA leaves them out.
Is my automaton uploaded anywhere?
No. Minimization runs entirely in your browser. Nothing you enter is sent to a server.