##### What is the minimum number of states in a non-deterministic finite automaton that accepts L?

Let w be any binary 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? what for dfa pls give suitable example

L will need (n+1) states for construction in nfa and (n+2) states for construction in dfa because we need 1 state i.e. trap state to reject strings which are not substrings of w.

Example, w = 110 then possible substrings are :ε,0,1,11,10,110

Good explanation.

very good explanation @shivani1234

I didn't quite get the question. Can someone elaborate it a bit?

## Pages