GATE CS 1992 Q02 — Regular Expressions and Finite Automata

To determine which identity is true, let us analyze each option by considering the languages they generate (assuming $r$ and $s$ represent distinct non-empty alphabets, e.g., $r = a$ and $s = b$):

• Option A: $(r^*)^* = r^*$
  The Kleene closure operation is idempotent. That is, applying the star operator multiple times does not generate any new strings beyond what is already in $r^*$. $$\text{LHS} = (r^*)^* = \{\epsilon\} \cup r^* \cup (r^*)^2 \cup \dots = r^* = \text{RHS}$$ Thus, this identity is TRUE.
• Option B: $r^* s^* = (r+s)^*$
  The language of the right-hand side, $(r+s)^*$, contains all possible strings over $r$ and $s$ in any order (e.g., $sr$). However, the left-hand side, $r^* s^*$, only generates strings where all occurrences of $r$ precede all occurrences of $s$. $$\text{Since } sr \in L((r+s)^*) \text{ but } sr \notin L(r^* s^*), \text{ the identity is } \mathbf{FALSE}.$$
• Option C: $(r+s)^* = r^* + s^*$
  The right-hand side generates strings consisting of only $r$'s or only $s$'s. It cannot generate mixed strings like $rs$. $$\text{Since } rs \in L((r+s)^*) \text{ but } rs \notin L(r^* + s^*), \text{ the identity is } \mathbf{FALSE}.$$
• Option D: $r^* s^* = r^* + s^*$
  The left-hand side can generate mixed strings like $rs$, whereas the right-hand side cannot. $$\text{Since } rs \in L(r^* s^*) \text{ but } rs \notin L(r^* + s^*), \text{ the identity is } \mathbf{FALSE}.$$