← Learn
Converter · step by step

DFA minimization

Every regular language has exactly one smallest DFA. Draw any DFA for the language and watch it shrink: the groups of states split step by step until only truly different states remain.

Watch it — strings ending in “ab”

This DFA is correct but wasteful: q3 does the same job as q0, q4 the same as q1, and q5 cannot be reached at all. States that still count as the same share a colour; watch the colours split until only real differences remain, then the groups merge into the three states the language needs.

Minimize1/4
The DFA · same colour = same group
aabbaabbaabbaabbaabbaba,bq0q1q2q3q4q5
Remove unreachable states
{q5} can never be reached from q0 and is removed.
How it works
1

Remove states that can never be reached

Anything not reachable from q0 has no effect on the language, so it goes first.

2

Split the states into accepting and non-accepting

These two groups are certainly different: the empty string already tells them apart.

3

Keep splitting groups whose members disagree

Two states stay together only if, for every symbol, they lead into the same group. Whenever they do not, the group is split. This repeats until nothing changes.

4

Merge each remaining group into one state

States still together cannot be told apart by any input, so one state can do the work of all of them.

Questions

Does the DFA have to be complete?

Yes — every state needs a transition for every symbol, which is what the simulator requires of a DFA anyway. It tells you which states are missing one.

What if my DFA is already minimal?

You are told so, and nothing new is opened. That is a quick way to check a hand-built answer.

Can I minimize an NFA?

Convert it to a DFA first, then minimize the result. Minimal NFAs are a much harder problem and are not unique.

More step-by-step tools