edited by
23,703 views
62 votes
62 votes

Let $w$ be any string of length $n$ in $\{0,1\}^*$. Let $L$ be the set of all substrings of $w$. What is the minimum number of states in non-deterministic finite automation that accepts $L$?

  1. $n-1$
  2. $n$
  3. $n+1$
  4. $2^{n-1}$
edited by

9 Answers

Best answer
23 votes
23 votes

Answer: C

For any string $w,$ let $L(w)$ be the set of all sub-strings of $w$.

For any alphabet $\Sigma ,$ if $w$ is a string of length $n$ over $\Sigma,$ then the number of states in a minimum state NFA  for $L(w)$ will be $n+1.$

Construction of such NFA with $n+1$ states is below :

Just accept the whole String $w$ first, we will have $n+1$ states for that. Now make every state final, also make epsilon transition from initial state to every state.

NOTE that we can also have a NFA without epsilon moves, with $n+1$ states. Just take the above $\epsilon-\text{NFA},$ and convert into NFA without $\epsilon-move,$ number of states will not change. (Proof is left for reader. Hint : See the $“\epsilon-\text{NFA}”$ to $“\text{NFA}$ without $\epsilon-move”$ conversion) 


Now, coming to number of states in Minimal DFA for $L(w) :$

This is interesting and much harder than it looks, also depends on size of alphabet $\Sigma.$

Result 1 :

If $| \Sigma | = 1 ( \text{i.e., unary alphabet}),$ then number of states in Minimal DFA for $L(w) = n+2.$ 

Proof :

Proof is extremely simple for this. Just accept string $w,$ , we need $n+2$ states, and make every state on the way a final state, except the last state which is dead state.


Result 2 :

If $| \Sigma | \geq 2 ,$ then number of states in Minimal DFA for $L(w)$ will be $|Q|$

where $n+2 \leq |Q| \leq 2n-1, when \,\, n\geq 3$

and $|Q| = n+2$ when $n \leq 2$

Proof of it is a matter for research students, should be skipped by GATE aspirants, But can be found below :

https://www.sciencedirect.com/science/article/pii/S0304397500000645

NOTE that number of states in minimal DFA for $L(w)$ may be more than $n+2, $ and one such counter example is string $w = abbba,$ the minimal DFA for $L(w)$ has $9$ states. Try creating this DFA.  

Another such counter example is string $w = abbbc,$ the minimal DFA for $L(w)$ has $9$ states. Try creating this DFA as well.  

Variation 1: https://gateoverflow.in/2342/gate-cse-2010-question-41?show=365317#c365317 

Variation 2: https://gateoverflow.in/2342/gate-cse-2010-question-41?show=372661#c372661 

edited by
78 votes
78 votes
We need a separate state for counting each distinct length. So, for length $n$ we need $n+1$ states (one for length zero). We don't need a reject state for larger strings as we need an NFA and not DFA. So, totally $n+1$ states are required.

Correct Answer: $C$
edited by
24 votes
24 votes

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}.

8 votes
8 votes
For n length string, the nfa needs n+1 states where all the states are final states and there are epsilon transitions from the initial state to all final states. So, answer is n+1.
Answer:

Related questions

40 votes
40 votes
1 answer
1
68 votes
68 votes
10 answers
2
27 votes
27 votes
3 answers
4
go_editor asked Apr 23, 2016
8,414 views
Consider the following Finite State Automaton:The minimum state automaton equivalent to the above FSA has the following number of states:$1$$2$$3$$4$