retagged by
467 views
2 votes
2 votes

Consider the following regular languages given below:

  •  L1 : Languages that accept strings over $\sum \left (a,b \right )$ , such that length of string is greater than $1$, but multiples of $3$.
  •  L2 : Languages that accept strings over $\sum \left (a,b \right )$ , such that every string contains at the most $2$ $a' s$ and $2$ $b' s$.
  •  L3 : Languages that correspond to following regular expression $R$:

                   $R =  10 + 0 + 11$ $0 * 1$  over $\sum \left ( 0,1 \right )$

Let the number of states in the minimized $DFA$ of each of it be $n1 ,n2 , n3$ respectively.

Then, which of the following is TRUE?

  1.     $n1 = n3 <  n2$
  2.     $n1 <  n3 <  n2$
  3.     $n3 < n1 < n2$
  4.     $n2 < n1 < n3$
retagged by

1 Answer

Best answer
2 votes
2 votes
If we draw the DFA for L1 , we will find that it have 4 states = n1

the DFA for L2 , we will find that it have 10 states  = n2

the DFA for L3 , we will find that it have 5 states = n3

which clearly satisfies the option B n1 <  n3 <  n2
selected by
Answer:

Related questions

2 votes
2 votes
1 answer
1
0 votes
0 votes
1 answer
3
Bikram asked Feb 9, 2017
308 views
Consider the grammar:$S\rightarrow$ $PQ | SQ | PS$$P\rightarrow k$$Q\rightarrow m$To get a set of $n$ terminals, the number of productions to be used are ______. $n^{2...