DFA Minimization

Why minimize?

A DFA built by hand, or produced automatically from a regular expression or an NFA, often has more states than it needs. Some states can never be reached, and some pairs of states do exactly the same job. A smaller DFA uses less memory in a lexer or a hardware circuit, and it is easier to understand.

Two states p and q are equivalent if, for every possible remaining input string, starting in p and starting in q give the same answer (accept or reject). Minimization merges each group of equivalent states into one state.

The algorithm (partition refinement)

1. Remove unreachable states. Run a BFS from the start state and delete everything it does not reach.
2. Initial split. Accepting and non-accepting states can never be equivalent, because on the empty input one accepts and the other rejects. Start with P = { accepting, non-accepting }.
3. Refine. For every state, write its signature: the group each symbol leads to. In each group, keep states together only if their signatures are equal. Otherwise split the group.
4. Repeat step 3 until a round splits nothing.
5. Merge. Every final group becomes one state of the minimal DFA.

Worked example: exactly one 1

The DFA in the 3D model has states q0…q6, start q0, accepting q2, q3, q4, q6:

• Unreachable: nothing leads to q6, so remove it.
• P₀ = { q2, q3, q4 } (accepting), { q0, q1, q5 } (non-accepting).
• Round 1. q0 and q1 go to non-accepting on 0 and to accepting on 1. q5 goes to non-accepting on both, so q5 splits off. q2, q3 and q4 all go to accepting on 0 and to q5’s group on 1, so they stay together.
• P₁ = { q2, q3, q4 }, { q0, q1 }, { q5 }.
• Round 2: no group splits. Done.

The minimal DFA has 3 states: {q0, q1} = “no 1 seen yet”, {q2, q3, q4} = “exactly one 1” (accepting), and {q5} = “two or more 1s” (a dead state).

Code

def minimize(states, alphabet, delta, start, accept):
    reach, todo = {start}, [start]                 # 1. reachable states
    while todo:
        s = todo.pop()
        for a in alphabet:
            if delta[s][a] not in reach:
                reach.add(delta[s][a])
                todo.append(delta[s][a])
    states = [s for s in states if s in reach]

    groups = [g for g in ([s for s in states if s in accept],
                          [s for s in states if s not in accept]) if g]
    while True:                                    # 2. refine until stable
        index = {s: i for i, g in enumerate(groups) for s in g}
        new = []
        for g in groups:
            buckets = {}
            for s in g:
                signature = tuple(index[delta[s][a]] for a in alphabet)
                buckets.setdefault(signature, []).append(s)
            new.extend(buckets.values())
        if len(new) == len(groups):
            return new                             # each group = one new state
        groups = new

d = {"q0": {"0": "q1", "1": "q2"}, "q1": {"0": "q0", "1": "q3"},
     "q2": {"0": "q4", "1": "q5"}, "q3": {"0": "q4", "1": "q5"},
     "q4": {"0": "q4", "1": "q5"}, "q5": {"0": "q5", "1": "q5"},
     "q6": {"0": "q4", "1": "q6"}}
print(minimize(list(d), "01", d, "q0", {"q2", "q3", "q4", "q6"}))
# [['q2', 'q3', 'q4'], ['q0', 'q1'], ['q5']]

Table-filling method

Many textbooks use the equivalent table-filling (Myhill–Nerode) method instead. Draw a triangle table of all state pairs. First mark every pair with one accepting and one non-accepting state. Then repeatedly mark a pair (p, q) if some symbol takes it to an already-marked pair. Pairs never marked are equivalent. It gives the same result as partition refinement and works well by hand for small DFAs.

Facts worth knowing

• The minimal DFA is unique (up to renaming states). This is the Myhill–Nerode theorem. So you can test whether two DFAs accept the same language by minimizing both and comparing them.
• A dead state (all transitions loop back to itself, not accepting) is reachable and must stay in a complete DFA. It is different from an unreachable state.
• NFAs have no such neat minimization; finding a minimal NFA is a much harder (PSPACE-hard) problem.

Common mistakes

• Merging states that look alike but differ in being accepting.
• Comparing the target states instead of the target groups. q2 → q4 and q3 → q4 match, but so would q2 → q4 and q3 → q3 if q3 and q4 are in the same group.
• Forgetting to remove unreachable states first.
• Stopping after one round. Refinement continues until a whole round causes no split.