edited by
2,574 views
21 votes
21 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)^*$
edited by

3 Answers

Best answer
24 votes
24 votes
  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.
edited by
6 votes
6 votes

Option D is a right choice.

Answer:

Related questions