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!
x(y+epsilon)*x
which can no longer contain an infinite amount ofx
s, unlike the initial regular expressions. $\endgroup$=
. $\endgroup$