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

A also accepts ba and ab .

B also accepts $\varepsilon$ .

D can’t generate both aa & bb  .

C is the answer.

---

All give aa bb plsx check

 

---

B is generating epsilon
A is generating single a or single b
D is generating at last (a+b)+

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

@Praveen Saini ji,   Long but awesome  approach.  Thank You. :)

---

i am not getting your 3rd digram can u please explain

---

that $(a+b)^*$ is bcoz of loop(closure) at state q3.

---

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

---

b^100 aa b^100 can be obtained through R
option C produce this string?

---

Has to be the best question of Regular expression !!

---

if someone use this method in exam , then he is ded , option elemination better

---

@Aryash_27 hello bro you are also preparing for 2027, can we connect??

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

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

---

so easy to understand thank you!

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

---

yes sutanay3 it is minimum length of 3 not 2 and ahwan's comment says exactly that.

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.

Answer 5

We will eliminate a given option

1--if it generates a new string that is not generated by given expression

Or

2--if it doesn't generate a string generated by the given expression

Option a- generates "ab" Which is not generated by given expression. So eliminated

Option b- same reason as option a

Option d- can't generate "bb" Which is generated by given expression. So eliminated.

So we are left with option c.Hence it is the answer.

If none of the above is given as a option, we have to check the option we are left with intuitively..

Answer 6

Option A: it can generate string like 'a' which is not a part of our language. So, rejected.

Option B: it generates NULL string, which is again not a part of our language.

Option C: it generates all our required strings. So it can be answer, since option D also looks similar.

Option D: it cannot generate string 'aa' or 'bb' which are the minimal length strings of our language. Hence, rejected.

So option C is therefore the right answer!