2
$\begingroup$

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 )

$\endgroup$
2
$\begingroup$

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)$

$\endgroup$
1
$\begingroup$

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 $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.