Minimising a DFA

Advanced

Introduction

Two DFAs can accept exactly the same language while one has many more states. Extra states cost memory in hardware and table space in software, and they make machines hard to compare. Minimisation removes every unnecessary state. A remarkable fact makes this more than tidying: for each regular language, the minimal DFA is unique, apart from the names of its states. So two DFAs accept the same language exactly when they minimise to the same machine.

How it works

Minimisation has two steps.

1. Remove unreachable states. Search from the start state, following every move. Any state never visited cannot affect the answer, so it can be deleted.

2. Merge equivalent states. Two states p and q are equivalent if, for every string w, reading w from p accepts exactly when reading w from q accepts. If some string tells them apart, it is a distinguishing string, and they must stay separate.

Testing every string is impossible, so we use partition refinement:

  1. Start with two groups: accepting states and non-accepting states. The empty string already distinguishes these.
  2. For each state, write its signature: the group each of its moves leads to, in symbol order.
  3. Split every group so that states with different signatures go to different groups.
  4. Repeat until a round splits nothing. Each remaining group is one state of the minimal DFA.

A group splits only when one of its states moves somewhere that is already known to behave differently, so states in the same final group can never be told apart. The method is sometimes called Moore's algorithm; Hopcroft's algorithm is a faster version of the same idea.

Syntax

groups = [sorted(accept), sorted(states - accept)]
while True:
    index = {q: i for i, g in enumerate(groups) for q in g}
    new = []
    for g in groups:
        by_sig = {}
        for q in g:
            by_sig.setdefault(tuple(index[delta[(q, c)]] for c in alphabet), []).append(q)
        new.extend(by_sig.values())
    if len(new) == len(groups): break
    groups = new

Example

alphabet = "01"
delta = {
    ("q0", "0"): "q1", ("q0", "1"): "q2",
    ("q1", "0"): "q1", ("q1", "1"): "q3",
    ("q2", "0"): "q1", ("q2", "1"): "q3",
    ("q3", "0"): "q1", ("q3", "1"): "q2",
    ("q4", "0"): "q4", ("q4", "1"): "q4",
}
start, accept = "q0", {"q2", "q3"}

reach, todo = {start}, [start]
while todo:
    s = todo.pop()
    for c in alphabet:
        t = delta[(s, c)]
        if t not in reach:
            reach.add(t)
            todo.append(t)
print("unreachable:", sorted({q for q, _ in delta} - reach))

groups = [sorted(reach & accept), sorted(reach - accept)]
rounds = 0
while True:
    rounds += 1
    index = {q: i for i, g in enumerate(groups) for q in g}
    new = []
    for g in groups:
        by_signature = {}
        for q in g:
            signature = tuple(index[delta[(q, c)]] for c in alphabet)
            by_signature.setdefault(signature, []).append(q)
        new.extend(by_signature.values())
    if len(new) == len(groups):
        break
    groups = new
print("groups:", groups, "after", rounds, "round(s)")
print("minimal DFA has", len(groups), "states")
Open in compiler

Line by line

  1. The DFA accepts binary strings that end in 1, but it was built carelessly: q2 and q3 both mean "the last symbol was 1", q0 and q1 both mean "it was not", and q4 can never be reached.
  2. The search from q0 visits q0 to q3, so q4 is reported as unreachable and ignored.
  3. The first groups are the accepting states [q2, q3] and the rest [q0, q1].
  4. In the first round every state in a group has the same signature: on 0 they all go to the non-accepting group, and on 1 to the accepting group. Nothing splits, so the refinement stops.
  5. Two groups remain, so the minimal DFA has two states, exactly the "ends in 1 or not" machine.

Expected result

unreachable: ['q4']
groups: [['q2', 'q3'], ['q0', 'q1']] after 1 round(s)
minimal DFA has 2 states

In the real world

Lexer generators minimise the DFAs they produce so that the tables in the final program are small. Hardware designers minimise state machines to save flip-flops on a chip. Tools that check whether two regular expressions mean the same thing minimise both DFAs and compare them.

Common mistakes

  • Merging states only because their moves look alike: the moves must lead to equivalent groups, not just similar ones.
  • Skipping the removal of unreachable states, so the result is not minimal.
  • Starting with a single group: accepting and non-accepting states are always different.
  • Minimising an incomplete DFA: add a dead state first, so that every state has every move.

Best practices

  • Remove unreachable states first; it makes every later step smaller.
  • Use the index of each state's group as its signature, so that comparing states is a tuple comparison.
  • Check the minimal DFA on the same test strings as the original one.

Summary

To minimise a DFA, delete unreachable states, then refine the partition into accepting and non-accepting states until no group splits. Each group becomes one state. The minimal DFA for a regular language is unique, so minimising is also a way to test whether two DFAs accept the same language.

Quick check

1. Which first partition does refinement start from?
2. When does a group of states split?
3. What is special about the minimal DFA of a regular language?
4. What should you do with unreachable states?

Key takeaways

  • First remove states you can never reach.
  • Start with two groups (accepting, non-accepting) and split any group whose members move to different groups.
  • When no group splits, each group becomes one state of the minimal DFA.

Practice problems for this lesson

My notes

Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.