DFA Minimization

How DFA Minimization works

Two states are equivalent when no string tells them apart — feed the same input to both and they either both accept or both reject. Minimisation finds those groups and collapses each to a single state. Partition refinement starts with the coarsest guess that is obviously right: accepting states in one block, non-accepting in another, because the empty string already separates them. Then it looks for evidence of a split. For each block and each alphabet symbol, ask where every member goes. If two members of a block land in different blocks, some string distinguishes them, so the block must be cut along those lines. Splitting is repeated until a full pass changes nothing — the partition is now stable. Each surviving block becomes one state of the minimal DFA, transitions are inherited from any representative, and the result is unique up to renaming.

Pseudocode

minimise(DFA D):
    remove states unreachable from D.start   // do this FIRST
    P = { F, Q \ F }                          // accepting | non-accepting
    if either block is empty: drop it

    repeat:
        changed = false
        for each block B in P:
            // group members by the tuple of blocks they move to
            signature(q) = ( blockOf(delta(q, a)) for each a in alphabet )
            split B into groups sharing the same signature
            if more than one group results:
                replace B in P with those groups
                changed = true
    until changed == false

    // build the quotient automaton
    states      = P
    start       = block containing D.start
    accepting   = blocks that are subsets of F
    delta(B, a) = block containing delta(any q in B, a)
    return minimal DFA

Time and space complexity

Time

O(n² · |Σ|) for naive refinement, O(n · |Σ| · log n) with Hopcroft

Space

O(n · |Σ|)

Each refinement round can split at most until every state is alone, so there are at most n rounds, and a round scans every transition. Hopcroft's algorithm gets the log n by always splitting against the smaller half of a block.

Worked example

DFA with states A,B,C,D,E over {0,1}. A→(0:B, 1:C), B→(0:B, 1:D), C→(0:B, 1:C), D→(0:B, 1:E), E→(0:B, 1:C). Accepting: {E}.

1. P0Split by acceptance: {E} | {A, B, C, D}.
2. Refine on 1Within {A,B,C,D}: A→C, B→D, C→C, D→E. D is the only one landing in the accepting block, so D splits off. P1 = {E} | {D} | {A, B, C}.
3. Refine again on 1Within {A,B,C}: A→C and C→C stay in {A,B,C}, but B→D lands in {D}. B splits off. P2 = {E} | {D} | {B} | {A, C}.
4. Check {A, C}On 0 both go to B (block {B}); on 1 both go to C (block {A,C}). Same signature — no split.
5. StableA full pass produces no new splits. Stop.

Four states instead of five: {A,C} merges into one. The minimal DFA is AC→(0:B, 1:AC), B→(0:B, 1:D), D→(0:B, 1:E), E→(0:B, 1:AC), start = AC, accepting = {E}.

Common exam mistakes

• Skipping the unreachable-state removal. Unreachable states can survive refinement and leave you with a DFA that is not actually minimal.
• Comparing where two states go instead of which block they go to. States can have different targets and still be equivalent, as long as those targets are in the same block.
• Stopping after one refinement pass. A split in one round often enables a split in the next; you stop only when a whole pass changes nothing.
• Forgetting that a missing transition still counts. If the DFA is partial, add the dead state explicitly, or two states will look equivalent when they are not.
• Assuming the answer depends on the order you split blocks in. It does not — the coarsest stable partition is unique, so any valid split order gives the same minimal DFA.

Frequently asked questions

Related simulators