Problem Detail: 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 … } $
Asked By : panthera onca
Answered By : A.Schulz
Take any $win {(L^*)}^R$. Then $w$ can be writen as $w=(u_1cdot u_2cdots u_n)^R$, with $u_iin L$. We have $$ w =(u_1cdot u_2cdots u_n)^R =u_n^R cdot u_{n-1}^R cdots u_1^R, $$ and therefore $win (L^R)^*$. Assume now that $win {(L^R)}^*$, then by the same argument $$ w =u_1^R cdot u_{2}^R cdots u_n^R= (u_ncdot u_{n-1}cdots u_1)^R , $$ and hence $win {(L^*)}^R$. As a consequence ${(L^*)}^R={(L^R)}^*$
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/3559
