Let w be any string of length n is {0,1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L?

Please explain this and thank you in advance.

Let w be any string of length n is {0,1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L?

Please explain this and thank you in advance.

For length, we need n+1 states(one for length 0). We didnâ€™t accept the dead state or the reject state because of the NFA. Therefore, minimum number of states in NFA that accepts L are n+1.

In DFA, it is n+2.