Let w be any string of length \(n\) in \(\{0, 1\}^*\). Let \(L\) be the set of…

Construction: build an NFA with n+1 states indexed 0..n.

• Create states q0, q1, …, qn and transitions qi --w[i+1]--> q(i+1) for i = 0..n−1 (these follow the characters of w).

• Make q0 the initial state and allow the machine to start matching at any position of w (for example, add ε-transitions from q0 to every qi).

• Make every state qi accepting (or at least q1..qn if you exclude the empty substring). Any substring corresponds to following the chain from some start position i to some end position j.

This construction uses n+1 states and accepts all substrings of w.

Lower bound (why fewer states cannot work):

Consider the n+1 distinct positions in w (positions 0 through n). For each position i, there is a set of continuations (strings you can read starting at i). If an NFA had fewer than n+1 states, two different positions would have to share the same NFA state. But then there would be a continuation that produces a substring when started from one position but not from the other, so the NFA would make the wrong acceptance decision. Therefore the NFA needs at least one distinct state per position, i.e. at least n+1 states.

Conclusion: The minimum number of states in a non-deterministic finite automaton that accepts the set of all substrings of w is n+1.