Topic: Theory of Computation
Consider the regular expression R over the alphabet {a,b}:
$R = (a^*b)^* + (b^*a)^*$
Which of the following regular expressions below describe the same language as R?
- A. $(a^*b^*) + (b^*a^*)$
- B. $a^*+b^*$
- C. $(a+b)^*$
- D. $a^*b+b^*a$
Answer: C. $(a+b)^*$
Explanation: The expression $(a^*b)^*$ generates all possible strings over {a,b} that end with 'b', as well as the empty string. The expression $(b^*a)^*$ generates all possible strings over {a,b} that end with 'a', as well as the empty string. The union of these two sets covers every possible string of 'a's and 'b's of any length. Therefore, $R$ is equivalent to the universal language $(a+b)^*$.