AdvancedTheory of Computation (TOC) · Lesson 9 of 14 · Updated ·
DFA Minimisation by Table Filling — Step-by-Step Marking, Distinguishing Strings and Checking Two DFAs Are Equal
The pumping lemma and minimisation lesson minimised a DFA by splitting groups (partition refinement). Most university exams and GATE answer keys use a different presentation of the same idea: the table-filling method, where you mark pairs of states in a triangular table. This lesson works through a full 8-state example the way you would on paper, then runs the same algorithm in Python so you can check your own answers.
1. The idea: which pairs can be told apart?
Two states p and q are distinguishable if some input string w takes one of them to an accepting state and the other to a non-accepting state. If no such string exists, p and q are equivalent and can be merged into one state without changing the language.
Table filling finds all distinguishable pairs by working backwards from the accepting states:
- Remove unreachable states (states no input can reach from the start).
- Draw a triangular table with one cell for every pair of states.
- Round 0: mark every pair where one state is accepting and the other is not. The empty string ε tells them apart.
- Round k: for each unmarked pair (p, q) and each symbol a, look at the pair (δ(p, a), δ(q, a)). If that pair is already marked, mark (p, q). (Reading a takes p and q to states that can be told apart, so p and q can be told apart too — by one more symbol.)
- Repeat until a round marks nothing new.
- Every unmarked pair is equivalent. Merge them.
A pair marked in round k has a distinguishing string of length exactly k. That is why the marks spread outwards from the accepting states, one symbol at a time.
2. The example machine
This 8-state DFA over {0, 1} is a classic textbook exercise. Start state A, accepting state C.
| State | on 0 | on 1 |
|---|---|---|
| → A | B | F |
| B | G | C |
| * C | A | C |
| D | C | G |
| E | H | F |
| F | C | G |
| G | G | E |
| H | G | C |
Step 1 — reachability. From A we reach B and F; from those G, C, E; from E we reach H. Nothing goes to D, so D is unreachable and is deleted. Seven states remain: A, B, C, E, F, G, H, giving 7·6/2 = 21 pairs.
3. Filling the table round by round
Round 0. C is the only accepting state, so every pair containing C is marked: (A,C), (B,C), (C,E), (C,F), (C,G), (C,H) — 6 pairs.
Round 1. Check each of the other 15 pairs. For example:
- (A, B): on 1, A → F and B → C. The pair (C, F) is marked, so mark (A, B).
- (A, E): on 0, A → B and E → H, giving (B, H), not marked yet. On 1, both go to F. Leave it.
- (B, H): on 0 both go to G; on 1 both go to C. Leave it — these two will never be separated.
Round 1 marks 11 pairs in total.
Round 2. (A, G): on 1, A → F and G → E, and (E, F) was marked in round 1, so mark (A, G). In the same way (E, G) is marked.
Round 3. Nothing new is marked, so we stop.
Only (A, E) and (B, H) are unmarked. Merging them gives five states:
| New state | on 0 | on 1 |
|---|---|---|
| → {A, E} | {B, H} | F |
| {B, H} | G | * C |
| * C | {A, E} | C |
| F | C | G |
| G | G | {A, E} |
4. The same algorithm in Python
from itertools import combinations
from collections import deque
delta = {"A": {"0": "B", "1": "F"}, "B": {"0": "G", "1": "C"}, "C": {"0": "A", "1": "C"},
"D": {"0": "C", "1": "G"}, "E": {"0": "H", "1": "F"}, "F": {"0": "C", "1": "G"},
"G": {"0": "G", "1": "E"}, "H": {"0": "G", "1": "C"}}
start, accepting = "A", {"C"}
reach, queue = {start}, deque([start]) # step 1: reachable states
while queue:
s = queue.popleft()
for t in delta[s].values():
if t not in reach:
reach.add(t)
queue.append(t)
states = sorted(reach)
print("unreachable:", sorted(set(delta) - reach))
marked = {pair: 0 for pair in combinations(states, 2) if (pair[0] in accepting) != (pair[1] in accepting)}
print("round 0 marks:", len(marked), "pairs")
rnd = 0
while True:
rnd += 1
new = {}
for p, q in combinations(states, 2):
if (p, q) in marked:
continue
for c in "01":
pair = tuple(sorted((delta[p][c], delta[q][c])))
if pair[0] != pair[1] and pair in marked:
new[(p, q)] = rnd
break
if not new:
break
print(f"round {rnd} marks: {len(new)} pairs", *([sorted(new)] if len(new) < 5 else []))
marked.update(new)
equivalent = [pair for pair in combinations(states, 2) if pair not in marked]
print("equivalent pairs:", equivalent)
unreachable: ['D']
round 0 marks: 6 pairs
round 1 marks: 11 pairs
round 2 marks: 2 pairs [('A', 'G'), ('E', 'G')]
equivalent pairs: [('A', 'E'), ('B', 'H')]
Notice that a new round only uses marks from earlier rounds. That keeps the round number equal to the length of the shortest distinguishing string, which the next section uses.
5. Finding the string that tells two states apart
A mark in the table is a promise: "some string distinguishes these two states". A breadth-first search over pairs of states finds the shortest such string. Start from the pair, try each symbol, and stop at the first pair where exactly one state accepts.
from collections import deque
delta = {"A": {"0": "B", "1": "F"}, "B": {"0": "G", "1": "C"}, "C": {"0": "A", "1": "C"},
"E": {"0": "H", "1": "F"}, "F": {"0": "C", "1": "G"},
"G": {"0": "G", "1": "E"}, "H": {"0": "G", "1": "C"}}
accepting = {"C"}
def distinguish(p, q):
seen, queue = {(p, q)}, deque([(p, q, "")])
while queue:
x, y, w = queue.popleft()
if (x in accepting) != (y in accepting):
return w or "ε"
for c in "01":
nxt = (delta[x][c], delta[y][c])
if nxt not in seen:
seen.add(nxt)
queue.append((*nxt, w + c))
return None # equivalent: no string works
for p, q in [("A", "C"), ("A", "B"), ("A", "G"), ("E", "G"), ("A", "E"), ("B", "H")]:
print(f"{p},{q}: {distinguish(p, q)}")
A,C: ε
A,B: 1
A,G: 01
E,G: 01
A,E: None
B,H: None
- (A, B) is told apart by
1: from A, reading 1 reaches F (reject); from B it reaches C (accept). Length 1 = round 1. - (A, G) needs
01: from A, 0 then 1 reaches C (accept); from G it reaches E (reject). Length 2 = round 2. - (A, E) and (B, H) return
None: no string separates them, which confirms the merge.
Writing the distinguishing string next to each mark is a good way to show your working in an exam answer.
6. Are two DFAs equal?
The same pair search answers a bigger question: do two DFAs accept exactly the same language? Run both machines together from their start states (the product construction). If you ever reach a pair where one accepts and the other rejects, the path to it is a counterexample. If no such pair is reachable, the DFAs are equivalent.
from collections import deque
def equivalent(d1, s1, f1, d2, s2, f2, alphabet="01"):
seen, queue = {(s1, s2)}, deque([(s1, s2, "")])
while queue:
x, y, w = queue.popleft()
if (x in f1) != (y in f2):
return False, w or "ε"
for c in alphabet:
nxt = (d1[x][c], d2[y][c])
if nxt not in seen:
seen.add(nxt)
queue.append((*nxt, w + c))
return True, None
original = {"A": {"0": "B", "1": "F"}, "B": {"0": "G", "1": "C"}, "C": {"0": "A", "1": "C"},
"D": {"0": "C", "1": "G"}, "E": {"0": "H", "1": "F"}, "F": {"0": "C", "1": "G"},
"G": {"0": "G", "1": "E"}, "H": {"0": "G", "1": "C"}}
minimal = {"AE": {"0": "BH", "1": "F"}, "BH": {"0": "G", "1": "C"}, "C": {"0": "AE", "1": "C"},
"F": {"0": "C", "1": "G"}, "G": {"0": "G", "1": "AE"}}
print("original vs minimal:", equivalent(original, "A", {"C"}, minimal, "AE", {"C"}))
wrong = {k: dict(v) for k, v in minimal.items()}
wrong["G"]["1"] = "G" # a copying mistake in one cell
print("original vs wrong: ", equivalent(original, "A", {"C"}, wrong, "AE", {"C"}))
original vs minimal: (True, None)
original vs wrong: (False, '00101')
The second check catches a one-cell mistake and even gives the input to try by hand. Use this to test your answers when you practise: if your minimal DFA is not equivalent to the original, the counterexample shows where you went wrong.
7. Facts to remember
| Fact | Detail |
|---|---|
| The minimal DFA is unique | up to renaming states (Myhill–Nerode theorem) |
| Number of states of the minimal DFA | = number of Myhill–Nerode classes of the language |
| Table filling cost | O(n²) pairs; a simple version takes O(n²·k·n) time for k symbols |
| Faster method | Hopcroft's algorithm, O(k·n log n) |
| Remove unreachable states first | otherwise they may be wrongly merged or counted |
| Dead (trap) states | equivalent dead states merge into one |
Common mistakes
- Skipping the reachability step. An unreachable state can look equivalent to a real one and give the wrong number of states.
- In round 0, marking pairs of two accepting states. Round 0 marks only accepting/non-accepting pairs.
- Marking (p, q) because δ(p, a) and δ(q, a) are different states. They must form a pair that is already marked.
- Stopping after one pass. Keep going until a full round marks nothing.
- Forgetting to redirect transitions after merging: every arrow into A or E must now go to {A, E}.
Quick recap
- Remove unreachable states; list all pairs in a triangular table.
- Round 0: mark accepting/non-accepting pairs. Round k: mark (p, q) if some symbol leads to an already-marked pair.
- Stop when a round adds nothing; unmarked pairs are equivalent and are merged.
- A pair marked in round k has a shortest distinguishing string of length k; BFS over pairs finds it.
- The same BFS on two machines tests DFA equivalence and returns a counterexample if they differ.