##### 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

shivani
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
8 Aug 2017 05:16 pm

Good explanation.

Sumit Verma
3 Aug 2017 02:29 pm

very good explanation @shivani1234

Nishant Mishra
8 Aug 2017 07:33 pm

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