DFA Minimization and Myhill–Nerode

Many different DFAs accept the same language. For every regular language there is a unique smallest DFA (up to renaming states), and there is an efficient algorithm to find it.

Two kinds of useless states

1. Unreachable states: no input string leads to them from the start state. Delete them.
2. Equivalent states: p and q are equivalent if, for every string w, δ̂(p, w) is accepting exactly when δ̂(q, w) is. Equivalent states behave the same in every future, so they can be merged.

Two states are distinguishable if some string w (a distinguishing string) leads one of them to an accepting state and the other to a non-accepting state. The empty string ε distinguishes every accepting state from every non-accepting one.

Partition refinement

The minimization algorithm starts by assuming that states are equivalent whenever it cannot yet tell them apart, and refines that guess:

1. Remove unreachable states.
2. Start with two groups: accepting states and non-accepting states (states that ε cannot distinguish).
3. Split a group whenever two of its states go, on some symbol, to different groups.
4. Repeat until no group splits. Each final group becomes one state of the minimal DFA.

After round k, two states are in the same group exactly when no string of length ≤ k distinguishes them.

Example over {0, 1}, with start state A and accepting states C, D and E:

def minimize(delta, start, accept, alphabet):
    reachable, todo = set(), [start]
    while todo:
        q = todo.pop()
        if q not in reachable:
            reachable.add(q)
            todo += [delta[q][a] for a in alphabet]
    print("unreachable:", sorted(set(delta) - reachable))
    groups = [g for g in (reachable & accept, reachable - accept) if g]
    round_no = 0
    while True:
        print(f"round {round_no}:", sorted(sorted(g) for g in groups))
        group_of = {q: i for i, g in enumerate(groups) for q in g}
        split = {}
        for q in sorted(reachable):
            key = (group_of[q],) + tuple(group_of[delta[q][a]] for a in alphabet)
            split.setdefault(key, set()).add(q)
        if len(split) == len(groups):
            return groups
        groups, round_no = list(split.values()), round_no + 1

delta = {"A": {"0": "B", "1": "C"}, "B": {"0": "A", "1": "D"}, "C": {"0": "E", "1": "F"},
         "D": {"0": "E", "1": "F"}, "E": {"0": "E", "1": "F"}, "F": {"0": "F", "1": "F"},
         "G": {"0": "G", "1": "A"}}
result = minimize(delta, "A", {"C", "D", "E"}, "01")
print("minimal DFA has", len(result), "states")

unreachable: ['G']
round 0: [['A', 'B', 'F'], ['C', 'D', 'E']]
round 1: [['A', 'B'], ['C', 'D', 'E'], ['F']]
minimal DFA has 3 states

• G is unreachable (nothing leads to it), so it is deleted.
• Round 0 separates {C, D, E} from {A, B, F}.
• In round 1, F leaves {A, B, F}: on 1, A and B go to accepting states (C, D), but F goes to F (non-accepting). The string 1 distinguishes them.
• In round 2 nothing splits, so A ≡ B and C ≡ D ≡ E.

The minimal DFA has 3 states: {A, B} = "no 1 yet", {C, D, E} = "exactly one 1 so far" (accepting), {F} = "two or more 1s" (a dead state). So the language is "strings containing exactly one 1".

The table-filling method

Textbooks often present the same idea as a table with one cell for every pair of states:

1. Mark every pair (accepting, non-accepting).
2. Mark a pair (p, q) if, for some symbol a, the pair (δ(p, a), δ(q, a)) is already marked.
3. Repeat until no new pair is marked. The unmarked pairs are the equivalent ones.

It gives exactly the same result; partition refinement is just the faster way to compute it.

The Myhill–Nerode theorem

Define two strings x and y to be equivalent with respect to L (x ≡_L y) if, for every string z, xz ∈ L exactly when yz ∈ L. In words: no continuation can tell x and y apart.

This gives a direct way to find the size of a minimal DFA: count the classes. For "strings ending in 01" there are three classes: strings ending in 0, strings ending in 01, and all the others (including ε). Every DFA state of the minimal DFA corresponds to one class.

It also proves languages non-regular. For L = {0ⁿ1ⁿ | n ≥ 0}, the strings 0, 00, 000, ... are pairwise inequivalent: 0ⁱ followed by 1ⁱ is in L, but 0ʲ followed by 1ⁱ is not (for i ≠ j). Infinitely many classes mean no DFA can accept L.

Practice questions