edited by
24,993 views
46 votes
46 votes

Consider the regular expression $(0 + 1) (0+1) \dots N$ times. The minimum state finite automaton that recognizes the language represented by this regular expression contains

  1. $n$ states
  2. $n+1$ states
  3. $n+2$ states
  4. None of the above
edited by

2 Answers

Best answer
76 votes
76 votes

As far as for above problem say regular expression for $(0+1)(0+1)\ldots 3$ times $=(0+1)(0+1)(0+1)$

Having DFA:

So, for regular expression $(0+1)(0+1)...N$ times we have $\mathbf{N+2}$ states in DFA 

$N+1$ states in NFA ( we can remove dead state) 

When question is about minimum state finite automata (and nothing is mentioned NFA/DFA) then which ever having minimum number must be taken which here is $N+1$ states. 

Correct Answer: $B$

edited by
12 votes
12 votes
(0+1)(0+1)......... n times

Length will be n..

No of states required for n length is n+1, one more for trap.. total n+2 states..
Answer:

Related questions

20 votes
20 votes
3 answers
1
Kathleen asked Sep 23, 2014
7,343 views
Context-free languages are closed under:Union, intersectionUnion, Kleene closureIntersection, complementComplement, Kleene closure
25 votes
25 votes
1 answer
2
Kathleen asked Sep 23, 2014
4,009 views
Let $R = (A, B, C, D, E, F)$ be a relation scheme with the following dependencies $C \rightarrow F, E \rightarrow A, EC \rightarrow D, A \rightarrow B $. Which one of the...
38 votes
38 votes
1 answer
3
Kathleen asked Sep 23, 2014
16,787 views
Consider the join of a relation $R$ with a relation $S$. If $R$ has $m$ tuples and $S$ has $n$ tuples then the maximum and minimum sizes of the join respectively are$m+n$...
21 votes
21 votes
6 answers
4
Kathleen asked Sep 23, 2014
22,945 views
Which of the following is the most powerful parsing method?LL (1)Canonical LRSLRLALR