Past exam question: 2082 Chaitra (Regular), Q5(b)
Open in the Padhaiko appQuestionGiven ε-NFAε-NFA
Convert the following automata into its equivalent DFA.
| State | a | b | ε |
|---|---|---|---|
| →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 :
- From state :
- On input : . (Accept state as ).
- On input : . .
- From state :
- On input : .
- On input : . (Accept state as ).
- From state :
- On input : (Accept state).
- On input : .
- From state :
- On input : .
- On input : .
- From state :
- On input : .
- On input : .
DFA Transition Table and Automaton Block: The resulting deterministic transition table is:
| DFA State | Subset | Input a | Input b |
|---|---|---|---|
| State | a | b |
|---|---|---|
| →A | B | C |
| *B | B | D |
| C | E | C |
| *D | E | D |
| *E | E | E |
- 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).