Test by Bikram | Theory of Computation | Test 2 | Question: 20

Question

Which of the following pairs of regular expressions define the same language $\{a, b\}$?

1. $(a^*+ b^*) ^*$  and  $(a+ b)^*$
2. $(a^* b )^* a^*$ and  $a(ba^* )^*$
3. $(a^*+ b)^*$ and $(a+ b)^*$
4. $(a b)^* a$  and  $a (ba)^*$

• A. $a, b$, and $d$
• B. $a, c$, and $d$
• C. $b,c,d$
• D. $a,b,c$ and $d$

Comments

in (ii), LHS is generating epsilon but RHS is not generating epsilon(RHS is genrating minimum string as 'a'),....rest all are equivalent.

so option B should be correct.

---

B is right answer

Answer 1

1) True, (a + b)* = Language contain all the string over the alphabet {a, b}.
(a* + b*)* = Language contain all the string over the alphabet {a, b}.

2) False. 
LHS = (a* b)* a*. Here a string can start either with a or b.
RHS = a(ba*). Here all the strings are starting with a.

3) True.
As LHS and RHS both contain all the string over the alphabet {a, b}.

4) True.
LHS = (ab)*a = abababab.....aba

$\Rightarrow$ a(ba)(ba)(ba).....(ba)(ba) = a(ba)* = RHS

Ans: Option B.