Test by Bikram | Mock GATE | Test 3 | Question: 36

Question

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?

• A.     $n1 = n3 <  n2$
• B.     $n1 <  n3 <  n2$
• C.     $n3 < n1 < n2$
• D.     $n2 < n1 < n3$

Comments

Sir , Solution to the above one please

---

@harsh

Draw the DFA's for these three languages and check which option satisfies.

---

L2={  ε, a, b, aa, ab, ba,bb}

DFA for L2 should have 4 states(including a dead state). Can anyone explain how DFA corresponding to L2 needs 10 states.

---

Note:

L2 is slight modification of L such that a's are multiple of 3 and b's are multiple of 3

Answer 1

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

Comments

sir please check n3 again it will have 4 states. so option a will be correct

---

n3 will have 5 states only , you must have forgot to add the dead state ,, i did the same mistake.