The Table-Filling Algorithm
What you'll learn: How to use the table-filling method to systematically find all pairs of distinguishable states in a DFA, setting the stage for minimization.
You've learned that two states are distinguishable if there exists some string that causes one to accept and the other to reject. But how do we find all such pairs efficiently? Enter the table-filling algorithm.
Core Idea
The algorithm uses a triangular table where each cell represents a pair of states. You progressively mark pairs as distinguishable by reasoning:
- Base case: Mark pairs where one state is accepting and the other is not (they differ on the empty string).
- Inductive step: For each unmarked pair
(p, q), check all alphabet symbols. If reading symbolasendsp → randq → s, and(r, s)is already marked as distinguishable, then(p, q)must also be distinguishable—mark it. - Repeat step 2 until no new pairs can be marked.
After the algorithm halts, unmarked pairs are indistinguishable and can be merged during minimization.
Why It Works
Think of it like a chain reaction: if two states lead to known distinguishable states on the same input, they themselves must be distinguishable. The table systematically propagates this knowledge backward through the DFA.
Example Sketch
For states {A, B, C} where A is accepting:
- Mark
(A,B)and(A,C)immediately (different acceptance). - If
BandCtransition to the same or unmarked pairs on all symbols, leave(B,C)unmarked—they're equivalent!
Key Takeaway:
The table-filling algorithm systematically marks all distinguishable state pairs by starting with obviously different states and propagating distinguishability through transitions.