Constructing the Minimal DFA
What you'll learn: How to build a minimal DFA by merging indistinguishable states identified by the table-filling algorithm.
The Core Idea
After using the table-filling algorithm to identify which states are indistinguishable (equivalent), you now have a partition of the original DFA's states into equivalence classes. Each class contains states that behave identically for all possible input strings. To construct the minimal DFA, you:
- Create one new state for each equivalence class in your partition
- Merge all states within each class into their representative state
- Redirect transitions to point to the appropriate equivalence class representatives
- Mark the new start state (the class containing the original start state)
- Mark new accepting states (any class containing at least one original accepting state)
The Merging Process
Think of equivalence classes like groups of identical employees doing the same job—you only need one representative from each group. If states q₁ and q₂ are indistinguishable, they become a single state in the minimal DFA, often labeled {q₁, q₂}.
For transitions: if the original DFA had δ(q₁, a) = q₃ and q₁ is in class C₁ while q₃ is in class C₃, the minimal DFA has δ'(C₁, a) = C₃.
The result is guaranteed to be the smallest possible DFA recognizing the same language—no further reduction is possible.
Key Takeaway: Constructing the minimal DFA means collapsing each equivalence class of indistinguishable states into a single representative state, creating the most efficient automaton for that language.