The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+33 votes
3.3k views

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}$
asked in Theory of Computation by Veteran (101k points)
edited by | 3.3k views
0
??
+1
how to create DFA for all possible substrings of a string ?

5 Answers

+43 votes
Best answer
We need a state for counting the 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 have NFA and not DFA. So, totally $n+1$ states are required. (For DFA it would be $n+2$).
answered by Veteran (357k points)
edited by
0
does substring include string itself .

e.g. let w=101

then substring may be e,0,1,00,11,01,10 rt ?
0
We cannot generalize that we need n+2 states for DFA.

eg: w=010  ; n=3

L={ ε , 0 , 1 , 01 , 10 , 101 }

Try drawing a DFA, it will have 7 states , which is not equal to n+2=5
0
^^ I dont think there will be 7 states for above
0

@Praveen Saini sir

How many then ? May be I am doing some mistake :)

0
It should be n + 1 where n is length of string
0
for nfa answer is n+1 states

But all dfa does not have dead state. for some of languages we have dead state for dfa.

so for dfa it can be n+1 or n+2 states

can anybody give perfect example.
0

 VS .we can make dfa with 4 state.

0
BEWARE: THE PICTURE WITH N+1 STATE IS NOT DFA. SEE (START STATE , 0 ) TRANSITION.
0

@abhishekmehta4u in your diagram edge from start state to finish state is not needed , if possible for you please change image

0
101 is not a substring of 010
+10 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}.

answered by Boss (12.3k points)
+1

Sir, why it is wrong to say that DFA for L contains "n+2" states

+1
well explained :)
+3 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
answered by (271 points)
edited by
0
Also can you help me with the substring of 'pratik' (assume input alphabet = a to z)

I guess you are just taking set of prefixes Union set of suffixes

According to me there are 2^6 substrings for the string 'pratik'
0
Hi,

Please tell me why '0' alone is not a substring. Also why empty string not a substring.

Thanks
+1
substrings are simply possible factors of the string. In this question we needed to find the states, so we need is only maximum possible substring of string, and maximum possible substring of any string is string itself
+1
yea 0, epsilon are also substrings of this string(updated in answer too)
0

@Pratikkumar Bulani  26 doesn't seems to be correct option to find all possible strings of length 6. I think for any given string w of length |W|=n, the number of possible strings (including null)= (n(n+1))/2 +1 where +1 is for epsilon.

Please check:https://gateoverflow.in/1660/gate1998-1-23

+3 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.
answered by Active (1.5k points)
+1 vote
  1. here substring requires all states makes as initial and final
answered by Junior (573 points)
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

39,529 questions
46,674 answers
139,824 comments
57,594 users