DFA Minimization Visualizer

Interactive automata builder with step-by-step Hopcroft minimization for teaching

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.

SYSTEM DESIGN

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.

SVG instead of Canvas for the automata diagram

SVG elements are DOM nodes with native hover states, click events, and accessibility attributes. Canvas requires manual hit-testing and custom event handling for every interaction. For a diagram where students click states and transitions to build and edit automata, SVG made every interactive behavior straightforward to implement. Canvas would have cost three times the code for the same result.

Adjacency list instead of adjacency matrix

DFA transition graphs are sparse. Most states do not have transitions to most other states on most input symbols. An adjacency list uses memory proportional to actual transitions rather than the square of the number of states, and makes iterating over a specific state's outgoing transitions direct. An adjacency matrix would have been wasteful in memory and required a full row scan for every transition lookup.

OUTCOMES

01Step-by-step Hopcroft minimization with forward and backward navigation through every partition state
02Interactive DFA and NFA construction via click and drag
03Used as a teaching aid in Theory of Computation coursework

STACK

React · JavaScript · SVG