Prove equivalence of two regex using basic identities.

68 Views Asked by At

I'm trying to prove the following identity

$$ (x+y)^* = (x^*y)^*x^* = x^*(yx^*)^* $$

Using the following 12 identities

  1. $L + M = M + L$
  2. $(L + M) + N = L + (M + N)$
  3. $(LM)N = L(MN)$
  4. $\emptyset + L = L + \emptyset = L$
  5. $\epsilon L = L \epsilon = L$
  6. $\emptyset L = L \emptyset = \emptyset$
  7. $L(M + N) = LM + LN$
  8. $(M+N)L = ML + NL$
  9. $L + L = L$
  10. $(L^*)^* = L^*$
  11. $\emptyset^* = \epsilon$
  12. $\epsilon^* = \epsilon$

My problem is that I cannot seem to get rid of the $*$ on the right side, no matter what I do. Any hint would really be appreciated.

1

There are 1 best solutions below

0
On

No, you cannot obtain your identity this way. Indeed, suppose you define $L^*$ by $L^* = \varepsilon + L$. Then the 12 identities are satisfied, but the new wanted one fails to be true.