PadhaikoAll subjects

Past exam question: 2082 Chaitra (Regular), Q5(a)

Theory of Computation · 3 marks

Open in the Padhaiko app

Topic: Closure Properties, Pumping Lemma & Decision Algorithms

Question

Explain 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:

  1. Eliminate Unreachable States: Remove all states that cannot be reached from the start state .
  2. 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 .
  3. Iterative Marking: For every unmarked pair and every input symbol , find the next-state pair . If is already marked, then mark .
  4. 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:

  1. Base marking: while . Thus, pairs and are marked.
  2. Examine unmarked pair :
    • On input : , which is unmarked.
    • On input : (identical state, unmarked).
  3. Pair remains unmarked. Therefore, .

Merging and into equivalence class yields a minimal 2-state DFA with states (start) and (accept).

Answer:

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.

All past exam questions for Theory of Computation