# Proving equivalency of regular expressions

x,y are regular expressions, prove this: (xy+x)$^*$x = x(yx+x)$^*$* (* in this expression is kleene star)

I am looking for a method that is applicable to prove such questions. I know that proof needs to show that:

1) (xy+x)$^*$x => x(yx+x)$^*$

2) x(yx+x)$^*$ => (xy+x)$^*$x

My attempt is like this:

1) (xy+x)$^*$x =

= x(y+epsilon)$^*$x by pulling x out -the x on the left is the one pulled out

= x(yx+x)$^*$ by distributing the last x

2) x(yx+x)$^*$

= x(y+epsilon)$^*$x by pulling the x out -the right x is the one pulled out

= (xy+x)$^*$x by distributing the first x

Does this make sense? Thanks!

• Your answer is not correct. In both 1 and 2 you end up with x(y+epsilon)*x which can no longer contain an infinite amount of xs, unlike the initial regular expressions. – orlp Sep 15 '18 at 7:26
• Algebraic approaches are fickleish. You need to have a theorem for every =. – Raphael Sep 15 '18 at 11:02
• Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. – Raphael Sep 15 '18 at 11:02