Partition Refinement: Minimizing a DFA by Splitting Blocks

Two states of a deterministic automaton are equivalent when no string distinguishes them: for every input, either both end in accepting states or neither does. Minimization merges every group of mutually equivalent states, and the result is the unique smallest DFA for the language, up to renaming. The algorithm that does this is not a search over strings. It is a refinement of a partition, and the whole of its behaviour follows from how that partition is split.

The initial partition and what it already knows

Start with two blocks: the accepting states and the rejecting states. States in different blocks are distinguishable by the empty string, since one accepts it and the other does not. If either block is empty, the initial partition has one block.

The refinement step is: for a block B and a symbol a, look at the set of states that transition into B on a. Call this the preimage of B under a. Every block C is then split into C ∩ preimage and C \ preimage. The states inside C ∩ preimage agree on where a sends them with respect to B, and the states in the complement do not, so they are distinguishable by a followed by whatever distinguishes B.

Repeat until no split changes the partition. At the fixed point, any two states in the same block agree on acceptance and on the block of every successor, so by induction on string length no string distinguishes them. The blocks are exactly the equivalence classes.

The naive implementation repeats the split for every block-symbol pair until stable. Each pass costs O(|Q| · |Σ|), and the number of passes is at most |Q| because each pass that changes anything adds at least one block, giving O(|Q|² · |Σ|). That is the Moore-style algorithm, and it is adequate for machines of a few hundred states. For machines with tens of thousands of states it is not, and the fix is not a better split rule but a better worklist.

Splitting the smaller half

The key observation is that a split of C into C ∩ P and C \ P produces one part that may be small, and the algorithm’s work can be charged to that smaller part. When splitting with respect to a preimage P, only the smaller of the two resulting pieces needs to be added to the worklist: the larger piece can be treated as “the old block minus the smaller piece”, and any future split that would have used the larger piece is equivalent to a split using the smaller one plus a split using the old block.

Concretely, maintain a worklist of splitters: pairs (block, symbol) whose preimage must be used to split other blocks. When a splitter (B, a) splits C into C₁ and C₂, push (C₁, b) for every symbol b if C₁ is the smaller piece, and do the same for C₂ if it is the smaller. Pushing both halves would be correct but would double the work at every level; pushing only the smaller half is what produces the logarithmic factor.

The accounting is the standard smaller-half argument. Each state can be in the smaller half of a split at most log₂ |Q| times, because each time it is, the block containing it at least halves in size. Each appearance generates one worklist entry per symbol, and processing an entry costs time proportional to the size of the preimage it defines. Summing over states gives O(|Q| · |Σ| · log |Q|), which is the Hopcroft bound.

from collections import deque

def minimize(delta, n, accept, nsym):
    """Hopcroft refinement. Returns (block id per state, blocks dict)."""
    reverse = [[[] for _ in range(n)] for _ in range(nsym)]
    for s in range(n):
        for a in range(nsym):
            reverse[a][delta[s][a]].append(s)       # predecessors, grouped by symbol

    block = [0 if accept[q] else 1 for q in range(n)]
    blocks = {0: {q for q in range(n) if block[q] == 0},
              1: {q for q in range(n) if block[q] == 1}}
    blocks = {k: v for k, v in blocks.items() if v}   # an empty side is not a block
    next_id = len(blocks)

    work = deque()                                    # splitters, as (block, symbol)
    for b in list(blocks):
        for a in range(nsym):
            work.append((b, a))

    while work:
        b, a = work.popleft()
        # Preimage of block b on a, from the reverse table: cost is set by the
        # splitter's size, not by |Q|.
        pre = {s for t in blocks[b] for s in reverse[a][t]}
        for cid in {block[s] for s in pre}:
            members = blocks[cid]
            hit = members & pre
            if not hit or hit == members:
                continue                              # wholly inside or outside: no split
            rest = members - hit
            # The larger piece keeps cid, so entries already queued for it stay valid;
            # only the smaller piece gets new work, which is what buys the log factor.
            if len(hit) <= len(rest):
                small, big = hit, rest
            else:
                small, big = rest, hit
            blocks[cid] = big
            blocks[next_id] = small
            for q in small:
                block[q] = next_id
            for x in range(nsym):
                work.append((next_id, x))
            next_id += 1

    return block, blocks

Three things in that loop are worth naming. The preimage is computed by scanning the splitter block’s members and looking up their predecessors in the reverse table, so the cost is proportional to the splitter size, not to |Q|. The set of blocks to examine comes from the preimage itself rather than a scan over all blocks, which is what keeps a pass proportional to the states it touches. And the worklist entry pushed for a split is a pair (block, symbol), never a bare block, because the preimage depends on both. Keeping the larger piece under its old identifier is what makes the “queue only the smaller half” rule safe: any entry already queued for that block still refers to the same, now larger, set of states.

What the algorithm needs from the data structure

A reverse transition table, indexed by symbol and then by target state, is the usual representation: for each symbol a and state t, the list of states s with δ(s, a) = t. Building it costs O(|Q| · |Σ|) time and the same in memory, and it makes the preimage of a block a concatenation of its members’ predecessor lists.

Without the reverse table, computing a preimage means scanning all states and testing membership of their successors, which is O(|Q|) per splitter and destroys the bound. This is the single most common implementation mistake: the algorithm is still correct, and its running time degrades to the naive quadratic behaviour while looking like the fast version.

Block membership must be testable in constant time. The block array above does that, and it is updated on every split. A set per block also works, with a slightly larger constant and more allocation.

The worklist can contain duplicates, and duplicates are harmless but cost time. A common optimization is to keep a per-block-and-symbol flag marking whether the pair is already queued, and to clear the flag when the entry is popped. The flag array needs one bit per block-symbol pair, so |Q| · |Σ| bits in the worst case before any splitting: for 100,000 states and a 64-symbol alphabet, 800 KB, and the array grows with each new block identifier.

Merging blocks into a machine

After refinement, the blocks are the states of the minimal machine. The start state is the block containing q₀; the accepting blocks are those containing accepting states; and the transition from block B on a is the block containing δ(q, a) for any q ∈ B. The last step is well defined precisely because all members of B agree on the target block, which is the invariant the refinement established.

Unreachable states must be removed before minimization, not after. An unreachable state forms a block of its own (or joins another block) and contributes a state to the output that no input can reach. Removing it afterwards gives the same language but requires a second reachability pass and a renumbering. Running reachability first costs one traversal and shrinks the input to the expensive algorithm, which is the better order.

The output is unique up to renaming: two minimal DFAs for the same language differ only by a bijection on states. That uniqueness is a theorem about the right congruence of the language, not a property of this particular algorithm, and it is what makes canonical forms possible for automata. The same minimal machine can be reached without any notion of state equivalence, by differentiating the regular expression that describes the language, which produces the residual languages directly.

Degenerate cases

A machine with no accepting states accepts nothing. The initial partition is one block containing every state, and no split can change it, because every preimage is either empty or the whole set. The result is a one-state machine with a self-loop on every symbol and no accepting state, which is the correct minimal form.

A machine whose language is all strings has every state accepting, and the same collapse happens. The result is a single accepting state, self-looping.

A machine with an incomplete transition function cannot be minimized as-is. The partition refinement assumes every state has a successor for every symbol; a missing transition has no target block, and the split rule cannot classify the state. Adding an explicit dead state and completing the table fixes this, and the dead state then either merges with existing rejecting states or survives as its own block. The complement construction in product constructions for intersection and complement runs into the same requirement.

Why minimize at all

Minimization is not an optimization of the machine’s speed. A smaller table has better cache behaviour, but the per-symbol cost is one load either way, and the difference between 1,000 and 900 states rarely changes a verdict. The reasons to minimize are different.

For equivalence and inclusion checks, the canonical form turns a language question into a graph isomorphism question, which is cheaper than a product construction over unreduced machines. For lexers emitted by a generator, the minimized table is the artifact that gets shipped, and a smaller artifact is easier to embed. For reasoning about a specification, the minimal machine is the smallest object that still exhibits the behaviour, which makes it the right thing to draw and the right thing to diff against a revised specification.

The cost is that minimization erases structure. The original machine’s states may correspond to recognizable phases of a protocol or positions in a pattern, and merging equivalent ones destroys that correspondence. Tools that report diagnostics usually keep the unreduced machine for error messages and minimize only the runtime artifact.