Past exam question: 2081 Chaitra (Regular), Q2(b)(ii)
Open in the Padhaiko appQuestion
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 :
- Start state :
- State :
- (Accept state, contains )
- (Accept state, contains )
- 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 State | NFA Subset | Input 0 | Input 1 |
|---|---|---|---|
| State | 0 | 1 |
|---|---|---|
| →q0 | q0 | q1 |
| q1 | q2 | q2 |
| *q2 | q2 | q2 |
- 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.