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)

Question

Quizplus · Accepted Answer

All three identities are true. (a) The order of union in regular expressions doesn't affect the language it generates, so (r + s)* and (s + r)* generate the same language. (b) Kleene star applied multiple times is equivalent to applying it once, so (r*)* = r*. (c) The expression (r* s*)* allows any number of r's followed by any number of s's, repeated any number of times, which is equivalent to any number of r's or s's in any order, represented by (r + s)*.

Consider the Following Identities for Regular Expressions: (A) (R