recategorized by
7,476 views
5 votes
5 votes

Consider the following identities for regular expressions :

(a) (r + s)* = (s + r)*

(b) (r*)* = r*

(c) (r* s*)* = (r + s)*

Which of the above identities are true ?

  1. (a) and (b) only
  2. (b) and (c) only
  3. (c) and (a) only
  4. (a), (b) and (c)
recategorized by

1 Answer

Best answer
5 votes
5 votes

all 3 are correct hence ans should be D 

(a) (r + s)* = (s + r)*    any string conrstructed by LHS can also be created by RHS and vice versa like  λ, r,s,rr,ss,rsrs..

b) (r*)* = r*  again valid as   (r*)* = r*.r*.r* .....possible strings are r,rr,rrr,rrrr... including  λ;

c) (r* s*)* = (r + s)*  LHS= (r*s*)(r*s*)(r*s*)......   so strings like  λ,r,s,rs,rsrs,srsr,rrrr,ssss,...are generated while RHS (r+s)* =(r+s)(r+s)...can also generate  λ,r,s,rs,rsrs,srsr,rrrr,ssss

selected by

Related questions