ToolSphere

DFA Minimizer

Computer science

Minimize a DFA step by step: unreachable states removed, the equivalence (partition) method and the table-filling method, with the minimal DFA drawn.

DFA minimizer

Draw your DFA, then press Minimize DFA. You get the smallest DFA for the same language, with both textbook methods step by step.

Minimized machine: 5 states. Equivalent-state groups: {C}; {A, E}; {G}; {B, H}; {F}. Unreachable states are removed first.

Starting example: the Hopcroft & Ullman 8-state DFA (start A, accepting C).

Your DFA (one arrow per symbol from each state)

Drag a state to move it. Click a state to make it start or accepting, rename or delete it.

0101010101010101ABCDEFGH

Step 1: remove unreachable states

No path from the start state reaches D, so it is dropped before minimizing.

Step 2: equivalence (partition) method

π₀: accepting vs non-accepting
{C} {A, B, E, F, G, H}
π₁: split by where each symbol leads
{C} {A, E, G} {B, H} {F}
π₂: split by where each symbol leads
{C} {A, E} {G} {B, H} {F}

π₂ splits no further, so its groups are the states of the minimal DFA.

Step 3: table-filling (Myhill–Nerode) method

B✕1
C✕0✕0
E≡✕1✕0
F✕1✕1✕0✕1
G✕2✕1✕0✕2✕1
H✕1≡✕0✕1✕1✕1
ABCEFG

✕0 marks pairs where one state accepts and the other does not; ✕n marks a pair whose transitions on some symbol lead to a pair marked earlier. Unmarked pairs (≡) are equivalent and merge. Hover a cell to see why.

Minimal DFA: 5 states

0101010101{C}{A,E}{G}{B,H}{F}

On this browser only

Give feedback

Did this tool help?

Tell us what worked, what didn’t, or what you’d like next.

Opens Google Forms in a new tab with this tool’s name filled in. No sign-in or email required. Feedback is optional.

Coming from JFLAP? See what carries over and what JFLAP still does better →

Try next

How to use DFA Minimizer

  1. 1Start from the textbook example, or clear it and draw your own DFA: 'Add State', then 'Add Transition' with one symbol per arrow (or a,b for several).
  2. 2Mark exactly one start state and any accepting states; every state should have one transition per symbol.
  3. 3Press 'Minimize DFA'.
  4. 4Read the three steps: unreachable states removed, the partition rounds π₀, π₁, …, and the filled table of distinguishable pairs.
  5. 5The minimal DFA is drawn underneath; each of its states is labelled with the original states it merges.

About DFA Minimizer

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.

Guides and tutorials

Frequently asked questions

How do I minimize a DFA?

Remove states that cannot be reached from the start state, then merge equivalent states. Find them either by the partition method (split {accepting} and {non-accepting} until no group splits) or by the table-filling method (mark every pair some string distinguishes). The groups or unmarked pairs that remain are the states of the minimal DFA.

What is the difference between the partition method and the table-filling method?

They find the same equivalent states. The partition (equivalence) method refines groups of states round by round, π₀, π₁, and so on. The table-filling (Myhill–Nerode) method works on pairs: it marks distinguishable pairs in a triangular table until nothing more can be marked. Courses teach one or the other; this calculator shows both.

Why must unreachable states be removed first?

Neither method looks at reachability, so an unreachable state survives as its own group or merges into a reachable one. In the textbook example, D is unreachable and also equivalent to F; keeping it does not change the language but leaves the DFA with a state it does not need.

Is the minimal DFA unique?

Yes, up to renaming states. Every DFA for the same regular language minimizes to the same number of states with the same structure, which is why minimizing two DFAs and comparing them is a way to check whether they accept the same language.

What if my DFA is missing some transitions?

A missing transition means the input is rejected from there, which is the same as going to a non-accepting dead state that loops on every symbol. The calculator adds such a trap state (shown as ⊥) while minimizing and drops it from the answer if it ends up alone.

Can I minimize an NFA here?

Not directly; minimization is defined for DFAs. Convert the NFA with the NFA to DFA converter first (subset construction), then minimize the result here. If you draw an NFA, the calculator tells you which state breaks the DFA rules.

Which algorithm does the calculator use?

Moore's partition refinement for the equivalence method and the standard table-filling algorithm for the Myhill–Nerode method, after a breadth-first search removes unreachable states. Both are run on every input and always agree. Hopcroft's algorithm finds the same answer faster but is rarely what exams ask you to show.

How many states can the minimal DFA have?

Never more than the reachable part of the original DFA, and at least one. It keeps exactly one state per class of equivalent states, so the count equals the number of groups in the final partition.

Have a suggestion for DFA Minimizer?Share your feedback ↗