THE PROBLEM
DFA minimization is one of the harder topics in Theory of Computation because the algorithm's intermediate states are invisible when you only see the final result. This tool makes every step of the minimization visible and navigable, so students can trace exactly what the algorithm is doing and why.
TRY IT — MINIMIZATION, LIVE
INPUT DFA
| state | on 0 | on 1 |
|---|
| a → | b | c |
| b | a | d |
| c* | e | f |
| d* | e | f |
| e* | e | f |
| f | f | f |
* accepting · → start state
PARTITION · ROUND 0
Start with the coarsest split that could possibly matter: accepting states {c, d, e} versus non-accepting states {a, b, f}. Everything else follows from refining this.
The rounds above are computed live by Moore’s partition-refinement algorithm running in your browser, a simpler illustration of the same splitting idea Hopcroft’s algorithm optimizes. The full C++ visualizer implements Hopcroft’s algorithm itself and animates its actual partition refinements step by step on arbitrary automata.
ENGINEERING DECISIONS
Hopcroft's algorithm instead of table-filling
Both correctly minimize DFAs. Table-filling is O(n²). Hopcroft is O(n log n). For a teaching tool where students might build large automata, the difference becomes visible at scale. More importantly, Hopcroft's partition-refinement approach maps directly onto a step-by-step visual: each partition refinement corresponds to exactly one screen update, making the algorithm's logic traceable without additional abstraction.
Step-by-step playback instead of instant output
The tool teaches minimization, not just produces the result. The algorithm runs to completion first and stores a snapshot of every intermediate partition state. Then the UI lets students step forward and backward through those snapshots independently. Separating execution from rendering entirely was the design decision that made both behaviors possible. Instant computation would have produced the correct answer with no pedagogical value.
Qt Widgets desktop app instead of a web tool
A QGraphicsScene/QGraphicsView canvas gives states and transitions native, hit-tested scene items with their own mouse events for free, so clicking, dragging, and selecting automaton elements needed no custom hit-testing layer. Distributed as a CMake-built C++17 desktop app rather than a browser tool, which also meant no serialization boundary between the UI and the minimization algorithm running underneath it.
Validating and completing the DFA before minimizing
Hopcroft's algorithm assumes a complete, deterministic input: every state needs an outgoing transition for every symbol in the alphabet. Real hand-drawn automata rarely start that way. The tool checks determinism and finds missing transitions first, then offers to add a sink state that absorbs every undefined transition, so minimization always runs on a well-formed DFA instead of failing or producing silently wrong partitions on an incomplete one.