← Quiz: NFA and Subset Construction: all 10 questions
Quiz: NFA and Subset Construction · Question 10 of 10
Why might a regex engine simulate the NFA directly instead of building the full DFA?
Why might a regex engine simulate the NFA directly instead of building the full DFA?
- A.NFAs recognise more languages
- B.The DFA can have exponentially many states, while simulating the NFA keeps memory small and time linear in the input
- C.DFAs cannot be stored in memory
- D.NFAs never need ε-moves
Answer & explanation
Correct answer: The DFA can have exponentially many states, while simulating the NFA keeps memory small and time linear in the input
This is the trade-off: fewer states but more work per symbol for the NFA.
Can you get the rest right without peeking?
Take the timed Quiz: NFA and Subset Construction quiz free. Pass it to earn XP and count towards your certificate.
Start the quiz →