What minimizing a DFA means
Two states are equivalent when no input string can tell them apart: from either one, exactly the same strings lead to acceptance. Merging every group of equivalent states, after throwing away states the start state can never reach, gives the minimal DFA: the smallest DFA for the language, and unique apart from the names of its states. Exam questions ask for it in two ways, and this calculator shows both, so you can follow whichever your course teaches and check one against the other.
Worked example: the 8-state textbook DFA
The preset is the classic example from Hopcroft and Ullman. The alphabet is {0, 1}, A is the start state and C is the only accepting state:
| State | on 0 | on 1 |
|---|---|---|
| → A | B | F |
| B | G | C |
| * C | A | C |
| D | C | G |
| E | H | F |
| F | C | G |
| G | G | E |
| H | G | C |
Step 1, unreachable states. From A you can reach B, F, G, C, E and H, but nothing ever leads to D, so D is dropped before minimizing.
Step 2, the equivalence (partition) method. Start with accepting against non-accepting states, then repeatedly split any group whose members go to different groups on some symbol:
- π₀ = {C} {A, B, E, F, G, H}
- π₁ = {C} {A, E, G} {B, H} {F}: on 1, B and H go to C while A, E and G stay among the non-accepting states, and F goes to C on 0.
- π₂ = {C} {A, E} {G} {B, H} {F}: on 0, A and E go to {B, H} but G goes to itself.
- π₃ = π₂, so the refinement has stopped.
Step 3, the table-filling (Myhill–Nerode) method. Write every pair of states in a triangular table. Mark each pair with one accepting and one non-accepting state (✕0). Then keep marking any unmarked pair whose transitions on some symbol lead to a pair that is already marked. Here round 1 marks pairs such as (A, B), because on 1 they go to F and C, and (C, F) was marked in round 0; round 2 marks (A, G) and (E, G). Nothing new is marked in round 3, and the pairs left unmarked are (A, E) and (B, H): the same answer as the partition method.
Result. The minimal DFA has five states: {A, E} (start), {B, H}, {C} (accepting), {F} and {G}. The calculator draws it and checks every step for you. If your answer has more states, look for an unreachable state you kept or a pair you forgot to mark in a later round.
Rules that trip people up
- Remove unreachable states first. Neither method removes them on its own. D above is equivalent to F, so skipping this step leaves a DFA that looks minimal but has an extra state.
- Keep refining until a round changes nothing. One round is rarely enough; a chain of n states can need n rounds.
- Missing transitions mean a dead state. If your DFA leaves out some transitions, the calculator adds a trap state (⊥) for them while minimizing, and leaves it out of the answer if it ends up on its own.
- The input must be a DFA. ε-moves or two arrows on the same symbol from one state make it an NFA; convert it first with the NFA to DFA converter.
Where this fits
Typical theory-of-computation pipeline: a regular expression becomes an NFA by Thompson's construction, the NFA becomes a DFA by the subset construction, and minimization then gives the smallest equivalent DFA. Draw and test any of them in the NFA & DFA simulator. The reasoning behind both methods is in the DFA minimization guide.