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

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 2

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!

Answer 3

Okay, so NULL string is an invalid string for our language.

Option B generates NULL string and hence, it can be straight away rejected.

Option A can generate strings like abab or baba which are invalid for our language, and hence they can be rejected.

Option C and D are well approximated answers, and look quite similar.

However both generate our required strings, but the difference is that Option D will never generate our minimal length strings 'aa' and 'bb'(You can check though!)

Hence, Option C will be indeed the right answer!

Answer 4

Option A is elimnated as it can generate ababab that can’t be produced from given R.E.

Option B generates “epsilon” not present in the given RE.

Option D can’t generate “aa”

So, C is answer.