# GATE2010-41

10.6k 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}$

edited
0
??
1
how to create DFA for all possible substrings of a string ?

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$).

Correct Answer: $C$

edited
3
Why answer is not n+2? for string of length n we need n+1 states and one extra state to reject the string of length greater than n.
1
Sir its an NFA, so here i dont think we need a reject state, we only need n+1 states for counting the length. Please clarify.
3
In NFA also we need dead state. @Omesh-Pandita can you confirm?
0
Sir a minimized NFA that accepts only "1" will have two states, 1 final and 1 non-final(start state) and a transition from non-final to final state on "1" and no other transitions... am I right ?
6

i don't think we need a dead state, the  transition function is Δ : Q × Σ → P(Q). P(Q) also includes empty set.

11

In NFA we do not need dead state.

http://www.eecs.wsu.edu/~ananth/CptS317/Lectures/FiniteAutomata.pdf

Page no 18.

For each state, not all symbols necessarily have to be defined in the transition function

3
Yes. I have corrected. But still we need n+1 states, for length 0, 1, ...., n.
0
Yes. You are right
1
for DFA n+2 states ?
0
@arjun sir how can u  say that  for dfa it would take n+2 states .    try this containing substring '11' it would take 3 states. for containing substring of length dfa always takes n+1 states. bcz here no trap states comes to be in picture . but if they ask starting wid then it will take 'n+2' states bcz here dead state is involved. am i correct plz verify @praveen saini sir @habib khan also
0
@Arjun sir, and all these n+1 states are final states right??
0
@Arjun Sir how n+2 for dfa ?
1

set2018 To reject other strings, one more state and self loop transitiion.

1

sir question is asking substring and not prefix of string so how n+1 states and also it is asked for NFA and not epsilon NFA .

0
does substring include string itself .

e.g. let w=101

then substring may be e,0,1,00,11,01,10 rt ?
1
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.
2

VS .we can make dfa with 4 state. 4
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
0
Same doubt....how can 101 be a substring oo 010?
0
hii arjun please me mail id to discuss it
0
This DFA doesn’t accept the substrings of 110
0

@balraj_allam

Language here is substrings of a any specific string and not substrings of all the strings..

0

What would be the answer had it been given maximum number of [email protected] sir

0
you can create infinite states in NFA using epsilon transitions.

Even if you are not using epsilon moves then also you can create infinite states for the given problem.
0

@Arjun For DFA, isn't it more accurate to say that we require at least n+2 states rather than saying that the minimum no of states required is n+2 ?

0

n+2 is sufficient to make a DFA for this language.

what will you do with one more state.

0
does DFA accepting all substrings always have minimum n+2 states ?

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

1

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

1
well explained :)
0

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

Exactly. The accepted answer stated that DFA would have "n+2" states which made me confused.

0
Best answer, cleared all doubts. Thanks
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.
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)

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

0

0 can be a substring  and if u want to accept 0 only then also 2 states will be needed because if u will loop of a in any state then not only one o but all zeros will be accepted...so if u want to accept only one one 0 then u have to make two states....A → B two states with 0 move.so  length of 0 is 1 and we need length+1 states.

1. here substring requires all states makes as initial and final 0
crop kar leta bhai ..😛
1 vote

In order to accept any string of length “n” with alphabet {0,1}, we require an NFA with “n+1” states. For example, consider a strings of length “3” such as “101”, the NFA with 4 states is given below: Since L is set of all substrings of “w” (Substring of a string is obtained by deleting any prefix or any suffix from string), so if we consider “w” as “101” , then the substrings of w are { ϵ, 0, 1, 10, 01, 101}.
Since the string “101” is also its substring, so we require 4 states (i.e. for n length string, n+1 states are required) and the NFA would be: Question is asking for set of all substrings to be accepted by nfa where a is of size n

So substrings possible are {€, 0,1,00,01,10,11} now draw nfa for this

q0---0,1-->q1--0,1-->q2 where all states are accepting state hence it's 3 for n=2 so n+1

## Related questions

1
6.7k views
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$ and $L3$ are context free. Only $L1$ and $L2$ are context free. All are context free
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 expressions below represents $L$? $(0^*10^*1)^*$ $0^*(10^*10^*)^*$ $0^*(10^*1)^*0^*$ $0^*1(10^*1)^*10^*$
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 necessarily true? $L_2 - L_1 \:\text{is recursively enumerable.}$ $L_1 - L_3 \:\text{is recursively enumerable.}$ $L_2 \cap L_3 \:\text{is recursively enumerable.}$ $L_2 \cup L_3 \:\text{is recursively enumerable.}$
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$