🎙 Free live masterclass · Sun, 29 Nov, 7:00 pm IST · Java Full Stack roadmap Register free →
Skills101
← 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?

  1. A.NFAs recognise more languages
  2. B.The DFA can have exponentially many states, while simulating the NFA keeps memory small and time linear in the input
  3. C.DFAs cannot be stored in memory
  4. 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 →