The Gateway to Computer Science Excellence
+15 votes
656 views

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 (29.9k points)
edited by | 656 views

3 Answers

+15 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 (16.3k points)
edited by
–1

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

+1
i think i have given the reason
'sr' can be generated from LHS but not RHS
+6
Hint for Option D -

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

can u take it from here ?
0
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∗)*
0
Hi..Please ignore..I got the answer.
+2 votes

Option D is a right choice.

by Active (4.9k points)
0
perfect!
0
whats X ...?
0 votes
by Junior (785 points)

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
50,666 questions
56,161 answers
193,776 comments
93,832 users