2
$\begingroup$

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 ... \} $

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

1 Answer 1

3
$\begingroup$

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)}^*$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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