PadhaikoAll subjects

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

Theory of Computation · 3 marks

Open in the Padhaiko app

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

Question

Convert the following automata into its equivalent DFA.

Given ε-NFAε-NFA
Given ε-NFA a, b b a ε a q0 q1 q2
Stateabε
→q0{q0}∅{q1}
q1{q2}{q1}∅
*q2{q2}{q2}∅
  • Machine-checked
  • ✓ accepts a
  • ✓ accepts ab
  • ✓ accepts aba
  • ✓ accepts bba
  • ✓ accepts aa
  • ✓ rejects ε
  • ✓ rejects b
  • ✓ rejects bb
  • ✓ rejects bbb

Solution

Epsilon-Closure Computation and Initial State: The given -NFA has transitions:

We compute the -closure for each state:

The start state of the equivalent DFA is:

Subset Construction Iteration: We compute transitions for each newly discovered subset on input symbols and using :

  1. From state :
    • On input : . (Accept state as ).
    • On input : . .
  2. From state :
    • On input : .
    • On input : . (Accept state as ).
  3. From state :
    • On input : (Accept state).
    • On input : .
  4. From state :
    • On input : .
    • On input : .
  5. From state :
    • On input : .
    • On input : .

DFA Transition Table and Automaton Block: The resulting deterministic transition table is:

DFA StateSubsetInput aInput b
Equivalent DFA from ε-NFADFA
Equivalent DFA from ε-NFA a, b b b a a b b a a A B C D E
Stateab
→ABC
*BBD
CEC
*DED
*EEE
  • Machine-checked
  • ✓ accepts a
  • ✓ accepts ab
  • ✓ accepts aba
  • ✓ accepts bba
  • ✓ accepts aa
  • ✓ accepts ba
  • ✓ rejects ε
  • ✓ rejects b
  • ✓ rejects bb
  • ✓ rejects bbb
Answer:

Using subset construction with -closures, the -NFA is transformed into a 5-state DFA with states (start), (accept), , (accept), and (accept).

All past exam questions for Theory of Computation