FOR FREE YEAR SOLVED

UGC NET 2016 

 

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?

 

A. (a) and (b) only

B. (b) and (c) only

C. (c) and (a) only

D. (a), (b) and (c)

 

Answer: 

 

(a) (r + s)* means set of all strings generated by r and s. 

Now (r + s)* = (s + r)*    any string constructed 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* i.e. λ, r, rr, rrr, rrrr which is same as r*.

 

(c) We already see in previous section (See all form of (a + b)*) i.e. (a*b*)* = (a + b)* 

If we derive (r* s*)* = (r*s*)(r*s*)(r*s*)...... we will get strings like λ, r, s, rs, rsrs, srsr, rrrr, ssss

And if we derive  (r + s)* = (r + s)(r + s)... it will give same strings like λ, r, s, rs, rsrs, srsr, rrrr, ssss.

 

So, (r* s*)* = (r + s)*

 

Here a, b, c all are true so, Option D is correct.