Register

GATE CSE 2010 | Question: 41

• edited by
38,999 views
88 88 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}$

10 Answers

Best answer
47 47 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
88 88 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
29 29 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}.

10 10 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.
4 4 votes
For example - string is 101 (n=3) then possible sub-strings are : (epsilon, 1,0,10,101,01,1) , so max length sub-string will be string itself.

And for accepting 'n' length string atleast 'n+1' states will be required ,either in DFA or NDFA (may require more states for acceptance of other sub-strings too)

So Answer is C)  n+1
• edited by
Page:
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GATE CSE 2010 | Ques...Next → · GATE CSE 2010 | Ques...
← Previous in category · GATE CSE 2010 | Ques...Next in category → · Toc theorem proof
Position:
Show:

Related questions

53 53 votes
2 answers 2 answers
18.0k
18.0k views
go_editor asked Sep 30, 2014
18,021 views
GATE CSE 2010 | Question: 40
Consider the languages$L1=\{0^i1^j\ \mid i \neq j\}, $$L2=\{0^i1^j\mid i=j\},$$L3=\{0^i1^j \mid i=2j+1\},$$L4=\{0^i1^j \mid i\neq2j\}$Only $L2$ is context free.Only $L2$ ...
92 92 votes
12 answers 12 answers
38.7k
38.7k views
go_editor asked Sep 30, 2014
38,731 views
GATE CSE 2010 | Question: 39
Let $L=\{ w \in \:(0+1)^* \mid w\text{ has even number of }1s \}$. i.e., $L$ is the set of all the bit strings with even numbers of $1$s. Which one of the regular express...
73 73 votes
3 answers 3 answers
26.0k
26.0k views
go_editor asked Sep 29, 2014
26,047 views
GATE CSE 2010 | Question: 17
Let $L_1$ be the recursive language. Let $L_2$ and $L_3$ be languages that are recursively enumerable but not recursive. Which of the following statements is not necessar...
97 97 votes
10 answers 10 answers
40.3k
40.3k views
go_editor asked Apr 21, 2016
40,318 views
GATE CSE 2010 | Question: 49
A computer system has an $L1$ cache, an $L2$ cache, and a main memory unit connected as shown below. The block size in $L1$ cache is $4$ words. The block size in $L2$ cac...