retagged by
590 views
2 votes
2 votes

Consider the following regular languages:

  • $L_1$: Languages that accept strings over $\Sigma = \{a, b\}$, such that length of string is greater than $1$, but multiple of $3$.
  • $L_2$: Languages that accept strings over $\Sigma = \{a, b\}$, such that every string contains at most $2 \ a$'s and at most $2 \ b$'s.
  • $L_3$: Languages that correspond to following regular expression $R$, where $R= 10+ 0+ 11 0^*1$ over $\Sigma =\{ 0, 1\}$.

Let the number of states in the minimal DFA of $L_1,L_2,L_3$  be  $s_1, s_2, s_3$ respectively. Then, which of the following is TRUE?

  1. $s_1 = s_2 < s_3$
  2. $s_1 = s_3 < s_2$
  3. $s_1 < s_2 < s_3$
  4. $s_1 < s_3 < s_2$
retagged by

3 Answers

Best answer
3 votes
3 votes

s1

s2

EDIT: we have to make the DFA so we should make one dead state in the above diagram 

 

s3

so option d is answer

 

edited by
0 votes
0 votes

Isn't dead state not counted? 

0 votes
0 votes

For S1 and S3 :-

AND For S2 :::

 

 

Answer:

Related questions

1 votes
1 votes
1 answer
2
Bikram asked Aug 12, 2017
463 views
Consider the following transition table of DFA where $q3$ is the final state:$\begin{array}{|c|c|c|} \hline {} & x & y \\ \hline \rightarrow q0 & q1 & q0 \\ \hline q1 & q...
1 votes
1 votes
1 answer
3
Bikram asked Aug 12, 2017
259 views
How many states does the Minimal Finite Automata that accepts all strings of $x$'s and $z$'s (where the number of $x$'s is at least $L$) contain?$L$ states$(L+1)$ states$...
1 votes
1 votes
1 answer
4
Bikram asked Aug 12, 2017
576 views
Consider the following input sequence $010101\dots$ ($01$ repeated one or more times).The minimum number of states required in a DFA to accept the strings following the a...