Subtopic 3 of 6
2.3NFA → DFA (subset construction)
Each DFA state is a set of NFA states closed under ε. Compute move(set, a) then ε-closure for each symbol. A DFA state is final if it contains an NFA final state.
| DFA state | NFA states (ε-closure) | on a | on b |
|---|---|---|---|
| A | {0,2,4,6,7,8} | B | C |
| B | {0,1,2,4,5,7,8,9,10} | B | D |
| C | {0,2,3,4,5,7,8} | B | C |
| D | {0,2,3,4,5,7,8,11,12} | B | E |
| *E | {0,2,3,4,5,7,8,13} | B | C |
* = final state (contains the NFA accept state 13). Worst case a DFA can have 2^n states for n NFA states.
Previous year questions: Lexical Analysis (2)
PYQs are grouped by topic, so this is the full set for Lexical Analysis; try the ones that match this subtopic. Open all 2 on the topic page.