🎙 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 7 of 10

An NFA accepts strings whose 4th symbol from the end is 1. How many states does the smallest DFA need?

An NFA accepts strings whose 4th symbol from the end is 1. How many states does the smallest DFA need?

  1. A.5
  2. B.8
  3. C.16
  4. D.4
Answer & explanation

Correct answer: 16

For the k-th symbol from the end, the DFA must remember the last k symbols: 2ᵏ = 16 states, while the NFA needs only k + 1 = 5.

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 →