← 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?
- A.5
- B.8
- C.16
- 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 →