is the following true $ (L^R)^* = (L^*)^R $

I tried the following to prove it true. let u,v belong to L then $ L^* = \{ u,v, uu, vv, uv, vu ... \} $ and $ (L^*)^R = \{ u^R, v^R, u^Ru^R, v^Rv^R, v^Ru^R, u^Rv^R ... \} $

now $ L^R = \{ u^R, v^R \} $ so $(L^R)^* = \{ u^R, v^R, u^Ru^R, v^Rv^R, u^Rv^R, v^Ru^R ... \} $

  • $\begingroup$ What have you tried thus far to prove that this is true? Or have you thought about (small) counter examples? $\endgroup$ Sep 15 '12 at 8:16
  • $\begingroup$ @DaveClarke : I have edited the question. I tried like this.. $\endgroup$ Sep 15 '12 at 11:02
  • $\begingroup$ Kleene's star is defined inductively, so maybe an induction works (if the statement is true). $\endgroup$
    – Raphael
    Sep 15 '12 at 13:01

Take any $w\in {(L^*)}^R$. Then $w$ can be writen as $w=(u_1\cdot u_2\cdots u_n)^R$, with $u_i\in L$. We have

$$ w =(u_1\cdot u_2\cdots u_n)^R =u_n^R \cdot u_{n-1}^R \cdots u_1^R, $$

and therefore $w\in (L^R)^*$.

Assume now that $w\in {(L^R)}^*$, then by the same argument $$ w =u_1^R \cdot u_{2}^R \cdots u_n^R= (u_n\cdot u_{n-1}\cdots u_1)^R , $$ and hence $w\in {(L^*)}^R$.

As a consequence ${(L^*)}^R={(L^R)}^*$


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.