Consider the following identities for regular expressions : (a) (r + s)* = (s…

All three identities are true. Short proofs:

• Identity (a): (r + s)* = (s + r)* because union is commutative: r + s = s + r, so taking Kleene star on both sides yields equal languages.

• Identity (b): (r*)* = r* because r* already contains all finite concatenations of strings from r (including the empty string), so applying the Kleene star again does not add any new strings.

• Identity (c): (r* s*)* = (r + s)*. Proof:

  - If a string belongs to (r* s*)*, it is a concatenation of blocks each of which is some number of r-strings followed by some number of s-strings; expanding those blocks shows the string is a concatenation of pieces each from r or s, so it lies in (r + s)*.

  - Conversely, any string in (r + s)* is a concatenation of items each from r or s. Group adjacent items of the same type into runs; each run lies in r* or s*, and pairing runs as r*-then-s* (allowing empty runs at ends) expresses the whole string as a concatenation of blocks from r* s*, so it lies in (r* s*)*.

Therefore, all three identities (a), (b), and (c) hold.