If RS is equivalent to SR, then R*S* is equivalent to S*R* (Proof by Contradiction)

Question

R and S are arbitrary regular expressions. I need a counter example where this is not true. I am unable to figure this out.

Answer 1

Suppose that $RS = SR$. I claim that $R^*S^* = S^*R^*$.

Step 1. Let us first show by induction on $m$ that for every $m \geqslant 0$, $$ (1) \quad RS^m = S^mR. $$ If $m = 0$, then $S^m = 1$, the language reduced to the empty word, and the result is trivial. If $m > 0$, then $RS^m = RSS^{m-1} = SRS^{m-1}$ and by the induction hypothesis $RS^{m-1} = S^{m-1}R$. Thus $RS^m = S^mR$.

Step 2. Let us prove by induction on $n$ that for all $n,m \geqslant 0$, $$ (2) \quad R^nS^m = S^mR^n. $$ Again, the case $n = 0$ is trivial. If $n > 0$, then $R^nS^m = RR^{n-1}S^m$ and by the induction hypothesis, $R^{n-1}S^m = S^mR^{n-1}$. It follows that $R^nS^m = RS^mR^{n-1}$. using (1), one gets $RS^m = S^mR$ and thus $R^nS^m = S^mRR^{n-1} = S^mR^n$ as required.

Final step. One has $$ R^*S^* = \Bigl(\sum_{n \geqslant 0} R^n\Bigr)\Bigl(\sum_{m \geqslant 0} S^m\Bigr) = \sum_{n, m \geqslant 0} R^nS^m = \sum_{n, m \geqslant 0} S^mR^n = \Bigl(\sum_{m \geqslant 0} S^m\Bigr)\Bigl(\sum_{n \geqslant 0} R^n\Bigr) = S^*R^* $$