GATE 2010 CS (CS1) – Question 51
Let w be any binary string of length n, and L the set of all its substrings. What is the minimum number of states in an NFA accepting L?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (C) n+1
Explanation
An n+1-state chain spelling w accepts substrings if every state is accepting and the initial state has ε-moves to each position. Conversely an accepting run for w visits at least n+1 distinct states along its n consumed symbols: repeating a state would permit pumping a nonempty segment, yielding arbitrarily long strings outside this finite language. Thus C.