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:
- Start with two groups: accepting states and non-accepting states. The empty string already distinguishes these.
- For each state, write its signature: the group each of its moves leads to, in symbol order.
- Split every group so that states with different signatures go to different groups.
- 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")Line by line
- 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.
- The search from q0 visits q0 to q3, so q4 is reported as unreachable and ignored.
- The first groups are the accepting states [q2, q3] and the rest [q0, q1].
- 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.
- 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
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.