Non deterministic Finite automaton


Let w be any string of length n is {0,1}*. Let L be the substring of w. What is the minimum number of states in a non- deterministic Finite automaton that accepts L?


The answer is : n+1
For n length string s, total n+1 state will be required(Here we are using NFA. so no need of reject state). To accept all the substring of string s, make all the state as final state, so total number of states will remain same i.e. n+1.


Suppose a string w from (0+1)* is 001 {n=3}
Step1. Draw a NFA that accept 001 so it requires (n+1=4) states

step2. Now our requirement is to draw a NFA for “L be the set of all substrings of w”. so From NFA given in step1 attach an branch containing ε from initial state to all other states. This ε-NFA accepts L.
— but there may be a confusion that it is a ε-NFA as i know that for an ε-NFA an equivalent NFA(w/o ε) contains same no of states as in ε-NFA
Hence this NFA also contains “n+1” states

Step3. now someone ask that how many minimum states DFA it requires to accept the L so i want to tell u that there is no any standard result for it and also it is wrong to say that DFA for L contains “n+2” states it is variying {u can check it also by taking some examples}.