Question

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

• A. $2^{n+1}$
• B. n + 1
• C. n
• D. n - 1

Answer 1

The correct option is B n + 1

Let w = "0110". To design a minimal NFA to accept all the substrings of this string, first accept the string itself as follows.

Now, to accept all the other substrings of "0110" make every state as starting state by using null moves and also make every state as final state.

The final NFA is shown below.

Since a string of length 4 requires 5 states, a string of length n will require n + 1 states.