[Solved]: Is star closure of reverse of language equivalent to reverse of closure of that language

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/3559