The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+34 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$?

- $n-1$
- $n$
- $n+1$
- $2^{n-1}$

+46 votes

Best answer

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

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**

** **answer should be

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

+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

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

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

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.

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

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

+12 votes

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

+5 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.

+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

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

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'

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

+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

0

@Pratikkumar Bulani 2^{6} 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

- All categories
- General Aptitude 1.5k
- Engineering Mathematics 7.1k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.3k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4k
- Non GATE 1.4k
- Others 1.5k
- Admissions 559
- Exam Queries 555
- Tier 1 Placement Questions 23
- Job Queries 69
- Projects 18

47,931 questions

52,335 answers

182,383 comments

67,817 users