Past exam question: 2082 Chaitra (Regular), Q5(a)
Open in the Padhaiko appExplain how can you minimize the state of DFA with example.
Solution
Table-Filling Algorithm and Equivalence Principles: DFA minimization produces a unique minimal-state DFA accepting the same regular language by merging indistinguishable (equivalent) states. Two states and are equivalent () if for all strings , .
The standard Table-Filling Algorithm (Myhill–Nerode equivalence) works as follows:
- Eliminate Unreachable States: Remove all states that cannot be reached from the start state .
- Initialize Lower-Triangular Table: For all pairs of distinct states , mark if one state is accepting and the other is non-accepting ( and or vice versa), because they are distinguished by .
- Iterative Marking: For every unmarked pair and every input symbol , find the next-state pair . If is already marked, then mark .
- Termination and Merging: Repeat until an entire pass completes without new marks. Unmarked pairs represent equivalent states and are collapsed into single equivalence classes.
Illustrative Example: Consider a DFA with states , input alphabet , start state , accept state , and transitions:
- ,
- ,
- ,
- Base marking: while . Thus, pairs and are marked.
- Examine unmarked pair :
- On input : , which is unmarked.
- On input : (identical state, unmarked).
- Pair remains unmarked. Therefore, .
Merging and into equivalence class yields a minimal 2-state DFA with states (start) and (accept).
DFA minimization removes unreachable states and iteratively applies the table-filling algorithm to separate distinguishable pairs. Unmarked pairs are indistinguishable and merged into equivalence classes, producing the minimal unique DFA.