How to prove that $R_1(R_2R_1)^* = (R_1R_2)^*R_1$; Theory of computation

Question

I need a formal proof for this property (or hints): Let $R_1$ and $R_2$ be to regular expressions : $R_1(R_2 R_1)^* = (R_1 R_2)^*R_1$

I don't know if the way I'm solving the problem is totally fine, but I'll share it :

Let $Q_1=R_1(R_2R_1)^*$ and $Q_2=(R_1R_2)^*R_1$ ; there are two cases :

• case 1 : $(R_2R_1)^*=\epsilon$ $\implies$ $Q_2=R_1$ ; we can find $R_1$ in the language described by $Q_2$ if $(R_1R_2)^* = \epsilon$ ; [...] in this case : $(R_2R_1)^*=\epsilon \Leftrightarrow (R_1R_2)^* =\epsilon $ and then $Q_2=Q_1$ .

• case 2 : $(R_2R_1)^*\neq \epsilon$ ( then $(R_1R_2)^*\neq\epsilon$ ) $\implies Q_1=R_1(R_2R_1)...(R_2R_1) = (R_1R_2)(R_1R_2)...(R_1R_2)R_1 = Q_2$

( $\epsilon$ = empty string )

Answer 1

Problem

$(R_2R_1)^*\neq(R_2R_1)...(R_2R_1)$ since $(R_2R_1)...(R_2R_1)$ has an "end" to it, and you haven't stated whether or not $\epsilon\in R_2R_1$ (which it is in $(R_2R_1)^*$ by definition).

Suggestion

You have the right idea, your proof just has a few technical problems. Since $R_1(R_2R_1)^*$ and $(R_1R_2)^*R_1$ are sets, you need to prove that, $R_1(R_2R_1)^*\subseteq (R_1R_2)^*R_1$ and $R_1(R_2R_1)^*\supseteq (R_1R_2)^*R_1$ to show that $R_1(R_2R_1)^*= (R_1R_2)^*R_1$ . To do this you should first prove that if $x\in (R_1R_2)^*R_1$ and $x\neq \epsilon \implies x\in (\prod\limits_{i=1}^{n}R_1R_2)R_1$ for some $n$. With that you can use your trick to show that $x\in R_1(R_2R_1)^*$.

Notes

$\prod\limits_{i=1}^{n} R_2R_1=(R_2R_1)...(R_2R_1)$ where there are $n$, $R_2R_1$'s.

Example: $\prod\limits_{i=1}^{3} R_2R_1=(R_2R_1)(R_2R_1)(R_2R_1)$

Answer 2

It suffices to come back to the definition of the star operator: $$ L^* = \bigcup_{n \geqslant 0} L^n $$ Now, using the fact that $R_1(R_2R_1)^n = (R_1R_2)^nR_1$, one gets $$ R_1(R_2R_1)^* = R_1\Bigl (\bigcup_{n \geqslant 0}\ (R_2R_1)^n \Bigr) = \bigcup_{n \geqslant 0}\ R_1(R_2R_1)^n = \bigcup_{n \geqslant 0}\ (R_1R_2)^nR_1 = \Bigl (\bigcup_{n \geqslant 0}\ (R_1R_2)^n \Bigr) R_1 = (R_1R_2)^*R_1 $$