The Gateway to Computer Science Excellence
+18 votes

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

  1. $(r + s)^* = r^*s^*$
  2. $r(s + t) = rs + t$
  3. $(r + s)^* = r^* + s^*$
  4. $(rs + r)^* r = r (sr + r)^*$
  5. $(r^*s)^* = (rs)^*$
in Theory of Computation by Boss
edited by | 799 views
This question was repeated in $\mathbf{2015}$ as well.

3 Answers

+19 votes
Best answer
  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.
by Boss
edited by

WHY NOT C option .....correct ...explain

i think i have given the reason
'sr' can be generated from LHS but not RHS
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



Hi..Please ignore..I got the answer.
+4 votes

Option D is a right choice.

by Loyal
whats X ...?

@Adarsh Pandey

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

+1 vote
by Junior

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,215 questions
59,965 answers
118,186 users