DFA Minimisation

Two states are equivalent if, for every possible string you could feed the machine from that point, both either accept or both reject. If no string distinguishes them, keeping both is pure waste — they do the same job.

You cannot test infinitely many strings, so the algorithm works backwards. It starts by assuming everything is equivalent, then repeatedly splits on evidence of difference until no more evidence can be found.

Alphabet (Σ)

The finite set of symbols the machine may read. For everything on this page, Σ = {a, b}.

String and language

A string is a finite sequence of symbols from Σ. A language is a set of strings — usually infinite. A machine does not compute a value; it answers one yes/no question about membership in a language.

State

The machine's entire memory. Not part of it — all of it. If two different inputs leave the machine in the same state, it can never again tell them apart.

Transition function (δ)

Where to go given the current state and the next symbol. For a DFA it is a function: exactly one answer, always. For an NFA it returns a set, possibly empty.

Accepting state

Drawn as a double circle. A string is accepted if the machine is in one of these when the input runs out — not if it merely passed through one on the way.

Trap or dead state

A non-accepting state with every symbol looping back to itself. Once you fall in you can never get out, so the answer is already no. Diagrams usually omit it and leave the arrow missing instead.

1. 1Remove unreachable states first — they cannot matter and would otherwise survive to the end.
2. 2Split into two blocks: accepting and non-accepting. The empty string already distinguishes these.
3. 3For each block, compute every state's signature: which block it lands in for each symbol.
4. 4Any block whose states have differing signatures splits into groups with matching signatures.
5. 5Repeat until a full pass causes no split.
6. 6Each surviving block becomes one state of the minimal DFA.

The process only ever splits. A block once separated is never rejoined, so it terminates in at most n rounds — you cannot split more times than you have states.

q1 and q3 have identical signatures and keep them on the next pass too, so they merge. q0 differs from both on b — it stays in the non-accepting block while they reach the accepting one — so it splits off. Four states become three.

• Minimal. No DFA for this language has fewer states — this is the Myhill-Nerode theorem, which says the minimum equals the number of distinguishable classes of prefix.
• Unique. Any two minimal DFAs for the same language differ only in what you call the states. No other machine model has this.
• A decision procedure. "Do these two DFAs accept the same language?" is answered by minimising both and checking for isomorphism.

That uniqueness is why minimisation matters beyond saving memory. It turns language equivalence — an infinite question — into a finite one.