GATE IT 2007 | Question: 73

Question

Consider the regular expression $R = (a + b)^* \ (aa + bb) \ (a + b)^*$

Which one of the regular expressions given below defines the same language as defined by the regular expression $R$ ?

• A. $(a(ba)^* + b(ab)^*)(a + b)^+$
• B. $(a(ba)^* + b(ab)^*)^*(a + b)^*$
• C. $(a(ba)^* (a + bb) + b(ab)^*(b + aa))(a + b)^*$
• D. $(a(ba)^* (a + bb) + b(ab)^*(b + aa))(a + b)^+$

Comments

B and D are completely wrong bcz not generate min string aa or bb  . and A is wrong bcz generate string  abab  which is not part of given R.E

---

got it thanks

---

A also accepts ba and ab .

B also accepts $\varepsilon$ .

D can’t generate both aa & bb  .

C is the answer.

Answer 1

$R = (a+b)^*(aa+bb)(a+b)^*$

Having,

Which is equivalent to the following Transition graph [by removing transition from $Q_1$ to $Q_2$ and $Q_2$ to $Q_1$ but does not affect the accepted language, be careful] and can be converted to an equivalent regular expression as shown below.

So, equivalent regular expression is $[a(ba)^*(a+bb) + b(ab)^*(b+aa)](a+b)^*$

Option C is answer.

Comments

Can't get why we are adding aa as a transition from q1 to q3 and bb as transition from q2 to q3 in the 3rd diagram?

---

pallaviamu

from q0 to q3 we accept abb and baa (diagram first)

when the array is removed (diagram 3) then it also accept abb and baa . so we need to add it.

---

Beautiful answer thank you sir

Answer 2

Another quick approach of solving this question for keen observers :-

Observe that $aa$ or $bb$ is minimal string that is possible in first Regular Expression $(a + b)^* (aa + bb) (a + b)^*.$

(A) We can have $ba$ or $ab$ as minimal strings which is not possible in $(a + b)^* (aa + bb) (a + b)^*$

(B) We can have empty string, which is not possible in $(a + b)^* (aa + bb) (a + b)^*.$

(D) Minimum string length is $3,$ $aa$ or $bb$ is not possible in this RE.

This rules out options A, B and D. So, option C must be the answer.

Comments

for the option  [D] we can not genrate three length string like { aaa,baa,aab}

which we can generate from R = (a + b)* (aa + bb) (a + b)* so this makes option D false

---

came here looking for exactly this kind of answer. the 'best answer' is quite difficult since we may not get a unique RE for a given DFA, and that itself can consume lot of time.

---

@best approch sir

Answer 3

> "abab" does not belong to the language but accepted by A & B. (Cancel them)
> "aa" belongs to the language, not accepted by D. Hence C is the ans. 

Comments

I think the language accepted by D are aaa,abbb,baa,bbbb not aa

Answer 4

B produces null. The given expr does not. So, B is eliminated.

A accepts abab. The given expr does not. So, A is eliminated. [P.S.: (a+b)+ does not produce null.]

The first bracketed part of both C and D produce a string with a substring of aa or bb, which is asked by the expr. But after that (a+b)+ cannot produce null. So, D is eliminated.

C is the answer.