TIFR CSE 2010 | Part B | Question: 34

Question

Let $r, s, t$ be regular expressions. Which of the following identities is correct?

• A. $(r + s)^* = r^*s^*$
• B. $r(s + t) = rs + t$
• C. $(r + s)^* = r^* + s^*$
• D. $(rs + r)^* r = r (sr + r)^*$
• E. $(r^*s)^* = (rs)^*$

Comments

This question was repeated in $\mathbf{2015}$ as well.

---

https://gateoverflow.in/29861/tifr2015-b-7

Answer 1

1. $(r + s)^* = r^*s^*$                    LHS can generate '$sr$' but RHS not
2. $r(s + t) = rs + t$                 LHS can generate '$rt$' but RHS not
3. $(r + s)^* = r^* + s^*$              LHS can generate '$sr$' but RHS not
4. $(rs + r)^* r = r (sr + r)^*$    They are equivalent
5. $(r^*s)^* = (rs)^*$                      LHS can generate '$rrrs$' but RHS not
   
   So option D is correct answer.

Comments

Hint for Option D -

$(rs + r)r= (rsr + rr) = r(sr+r)$ (post multiply and then pre common )

can u take it from here ?

---

Hi I have a doubt here.

 

 

(r+s)∗= can generate sr

Can you explain how (r∗s∗)* generates sr

 

In other words how they are equivalent

 

 

(r+s)∗=(r∗s∗)*

---

Hi..Please ignore..I got the answer.

Answer 2

Option D is a right choice.

Comments

perfect!

---

whats X ...?

---

@Adarsh Pandey

He took (s+epsilon) as X.. Which is just a variable..

---

How does the given identity at the end hold?

It should be (pq)*p=p*(qp).

Answer 3

https://gateoverflow.in/29861/tifr2015-b-7