Course contentsShow
← Computer Science
Lesson 1789 of 2,87240. Theory of Computation: Regular LanguagesFree lesson

The Table-Filling Algorithm

Using the table-filling method to systematically identify all pairs of distinguishable states for DFA minimization.

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:

  1. Base case: Mark pairs where one state is accepting and the other is not (they differ on the empty string).
  2. Inductive step: For each unmarked pair (p, q), check all alphabet symbols. If reading symbol a sends p → r and q → s, and (r, s) is already marked as distinguishable, then (p, q) must also be distinguishable—mark it.
  3. 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 B and C transition 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.