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

4Comments
shivani @shivani1234
3 Aug 2017 12:10 pm

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 

SaiCharan @kotlasaicharan
8 Aug 2017 05:16 pm

Good explanation. 

Sumit Verma @sumitverma
3 Aug 2017 02:29 pm

very good explanation @shivani1234

Nishant Mishra @nishantmishra02
8 Aug 2017 07:33 pm

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

Pages