Answer: C
For any string $w,$ let $L(w)$ be the set of all sub-strings of $w$.
For any alphabet $\Sigma ,$ if $w$ is a string of length $n$ over $\Sigma,$ then the number of states in a minimum state NFA for $L(w)$ will be $n+1.$
Construction of such NFA with $n+1$ states is below :
Just accept the whole String $w$ first, we will have $n+1$ states for that. Now make every state final, also make epsilon transition from initial state to every state.
NOTE that we can also have a NFA without epsilon moves, with $n+1$ states. Just take the above $\epsilon-\text{NFA},$ and convert into NFA without $\epsilon-move,$ number of states will not change. (Proof is left for reader. Hint : See the $“\epsilon-\text{NFA}”$ to $“\text{NFA}$ without $\epsilon-move”$ conversion)
Now, coming to number of states in Minimal DFA for $L(w) :$
This is interesting and much harder than it looks, also depends on size of alphabet $\Sigma.$
Result 1 :
If $| \Sigma | = 1 ( \text{i.e., unary alphabet}),$ then number of states in Minimal DFA for $L(w) = n+2.$
Proof :
Proof is extremely simple for this. Just accept string $w,$ , we need $n+2$ states, and make every state on the way a final state, except the last state which is dead state.
Result 2 :
If $| \Sigma | \geq 2 ,$ then number of states in Minimal DFA for $L(w)$ will be $|Q|$
where $n+2 \leq |Q| \leq 2n-1, when \,\, n\geq 3$
and $|Q| = n+2$ when $n \leq 2$
Proof of it is a matter for research students, should be skipped by GATE aspirants, But can be found below :
https://www.sciencedirect.com/science/article/pii/S0304397500000645
NOTE that number of states in minimal DFA for $L(w)$ may be more than $n+2, $ and one such counter example is string $w = abbba,$ the minimal DFA for $L(w)$ has $9$ states. Try creating this DFA.
Another such counter example is string $w = abbbc,$ the minimal DFA for $L(w)$ has $9$ states. Try creating this DFA as well.
Variation 1: https://gateoverflow.in/2342/gate-cse-2010-question-41?show=365317#c365317
Variation 2: https://gateoverflow.in/2342/gate-cse-2010-question-41?show=372661#c372661