PadhaikoAll subjects

Past exam question: 2082 Kartik (Back), Q2(c)

Theory of Computation · 3 marks

Open in the Padhaiko app

Topic: Closure Properties, Pumping Lemma & Decision Algorithms

Question

Minimize the given DFA.

01
BC
BAD
EF
EF
EF
FFF

Solution

Table-Filling Algorithm Step-by-Step: The DFA has state set , start state , accept states , and non-accepting states . All states are reachable from (, , , , ).

  1. Initial 0-Equivalence Partition: Any accept state and non-accept state are distinguishable: pairs between and are marked. Unmarked pairs: and .
  2. Evaluate Unmarked Accepting Pairs :
    • For all three states , on input 0 they transition to , and on input 1 they transition to .
    • Hence, or , neither of which is marked.
    • Thus, .
  3. Evaluate Unmarked Non-Accepting Pairs :
    • Pair : On input 1, (accept) while (non-accept). Since is marked, mark .
    • Pair : On input 1, (accept) while (non-accept). Mark .
    • Pair :
      • On input 0: , which is unmarked.
      • On input 1: . But (unmarked).
      • Therefore, pair remains unmarked, so .

Minimized DFA Transition Table and Automaton: The equivalence classes are:

Minimized Transition Table:

StateInput 0Input 1
Minimized DFADFA
Minimized DFA 0, 1 0 0 1 1 q0 q1 q2
State01
→q0q0q1
*q1q1q2
q2q2q2
  • Machine-checked
  • ✓ accepts 1
  • ✓ accepts 01
  • ✓ accepts 001
  • ✓ accepts 10
  • ✓ accepts 010
  • ✓ accepts 000100
  • ✓ rejects ε
  • ✓ rejects 0
  • ✓ rejects 00
  • ✓ rejects 11
  • ✓ rejects 011
  • ✓ rejects 101
  • ✓ rejects 110
Answer:

States and merge into single states. The minimal DFA has 3 states: (start), (accept), and (dead state).

All past exam questions for Theory of Computation