Register

GATE CSE 2010 | Question: 41

• edited by
23,953 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
User Avatar

9 Answers

0 votes
0 votes

Since its asked ib NFA, remember NFA accepts only set of valid strings. For the given language, the maximum length of sub-string will be the trivial one i.e. the string itself of length N. So to get the trivial string accepted “n+1” states are required and for the rest of strings we can make multiple transitions in single states. Hence option C is correct

User Avatar
Page:
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

41 votes
41 votes
1 answer
1
go_editor asked Sep 30, 2014
11,853 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$ and $L3$ are context free. Only $L1$ and $L2$ are context free. All are context free
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$ ...
User Avatar
68 votes
68 votes
10 answers
2
go_editor asked Sep 30, 2014
22,344 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 expressions below represents $L$? $(0^*10^*1)^*$ $0^*(10^*10^*)^*$ $0^*(10^*1)^*0^*$ $0^*1(10^*1)^*10^*$
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...
User Avatar
27 votes
27 votes
3 answers
4
go_editor asked Apr 23, 2016
8,475 views
GATE CSE 2007 | Question: 75
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$
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$
User Avatar
Link Copied!