PadhaikoAll subjects

Past exam question: 2081 Chaitra (Regular), Q2(b)(ii)

Theory of Computation · 4 marks

Open in the Padhaiko app

Topic: NFA, ε-NFA & Their Equivalence with DFA

Question

Convert the given NFA into equivalent DFA.

Solution

Analysis of the Given NFA: From the diagram, the NFA has transitions:

Notice there are no -transitions, so for all subsets .

Subset Construction Step-by-Step: We compute transitions for all reachable subsets of states from initial state :

  1. Start state :
  2. State :
    • (Accept state, contains )
    • (Accept state, contains )
  3. State :

No additional subsets are generated. The DFA has exactly 3 reachable states.

DFA Transition Table and Automaton Block: The transition table of the equivalent DFA is:

DFA StateNFA SubsetInput 0Input 1
Equivalent DFA from NFADFA
Equivalent DFA from NFA 0, 1 0 1 0, 1 q0 q1 q2
State01
→q0q0q1
q1q2q2
*q2q2q2
  • Machine-checked
  • ✓ accepts 10
  • ✓ accepts 11
  • ✓ accepts 010
  • ✓ accepts 011
  • ✓ accepts 0010
  • ✓ accepts 100
  • ✓ accepts 111
  • ✓ rejects ε
  • ✓ rejects 0
  • ✓ rejects 1
  • ✓ rejects 00
  • ✓ rejects 01
  • ✓ rejects 000
Answer:

Using subset construction, the NFA converts to a 3-state DFA with states (start), , and (accept). Language recognized is , accepting all strings containing at least one followed by any subsequent symbol.

All past exam questions for Theory of Computation