Prove that $(L^R)^* = (L^*)^R$ for all languages L

Question

I don’t know how to formally prove it. It’s obvious to see that whether first we reverse strings of L then star it or we star it and then reverse all the strings, the result will be the same. How would I go about formally proving it ?

Answer 1

To prove the statement for the Kleene star, means proving $(L^R)^{n}=(L^{n})^R$ for arbitrary $n\in\mathbb N$. To prove equality of sets is often done by proving $(L^R)^{n}\subseteq(L^{n})^R$ and $(L^R)^{n}\supseteq(L^{n})^R$.

I will do just the $\subseteq$ case, and only partly, since it should be quite easy:

Let $s\in(L^R)^{n}$, then $s=\overline{t}_0\overline{t}_1\dots\overline{t}_n$, where each $\overline t_i$ is a string in $L^R$, and therefore is the reverse of a string $t_i$ in $L$.

Then the reverse of $s$ is a string in $L^n$ (why?), and thus $s\in(L^n)^R$.

Answer 2

$$\begin{array}{l}\forall w \in {({L^R})^*},\;\;\;w = {w_1}{w_2}...{w_l}\;\;|\;\;{w_i} \in {L^R}\\ \to {w^R} = {({w_1}{w_2}...{w_l})^R} = w_l^R...w_2^Rw_1^R\;\;|\;\;{w_i} \in {L^R}\\ \to {w^R} = w_l^R...w_2^Rw_1^R\;\;|\;\;{w_i} \in {L^R} \to {w^R} = w_l^R...w_2^Rw_1^R\;\;|\;\;w_i^R \in L \to {w^R} \in {L^*}\\ \to w \in {({L^*})^R} \to {({L^R})^*} \subseteq {({L^*})^R}\;\;\;\;(A)\\\forall w \in {({L^*})^R},\;\;\;{w^R} \in {L^*} \to {w^R} = {w_1}{w_2}...{w_l}\;\;|\;\;{w_i} \in L\\ \to w = {({w_1}{w_2}...{w_l})^R} = w_l^R...w_2^Rw_1^R\;\;|\;\;{w_i} \in L\\ \to w = w_l^R...w_2^Rw_1^R\;\;|\;\;{w_i} \in L \to w = w_l^R...w_2^Rw_1^R\;\;|\;\;w_i^R \in {L^R}\\ \to w \in {({L^R})^*} \to {({L^*})^R} \subseteq {({L^R})^*}\;\;\;\;(B)\\(A),\;(B) \to \left\{ {\begin{array}{*{20}{c}}{{{({L^R})}^*} \subseteq {{({L^*})}^R}}\\{{{({L^*})}^R} \subseteq {{({L^R})}^*}}\end{array}} \right. \to {({L^R})^*} = {({L^*})^R}\end{array} % MathType!MTEF!2!1!+- % feaahqart1ev3aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiFu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGceaqabeaacqGHai % IicaWG3bGaeyicI4SaaiikaiaadYeadaahaaWcbeqaaiaadkfaaaGc % caGGPaWaaWbaaSqabeaacaGGQaaaaOGaaiilaiaaysW7caaMe8UaaG % jbVlaadEhacqGH9aqpcaWG3bWaaSbaaSqaaiaaigdaaeqaaOGaam4D % amaaBaaaleaacaaIYaaabeaakiaac6cacaGGUaGaaiOlaiaadEhada % WgaaWcbaGaamiBaaqabaGccaaMe8UaaGjbVlaacYhacaaMe8UaaGjb % VlaadEhadaWgaaWcbaGaamyAaaqabaGccqGHiiIZcaWGmbWaaWbaaS % qabeaacaWGsbaaaaGcbaGaeyOKH4Qaam4DamaaCaaaleqabaGaamOu % aaaakiabg2da9iaacIcacaWG3bWaaSbaaSqaaiaaigdaaeqaaOGaam % 4DamaaBaaaleaacaaIYaaabeaakiaac6cacaGGUaGaaiOlaiaadEha % daWgaaWcbaGaamiBaaqabaGccaGGPaWaaWbaaSqabeaacaWGsbaaaO % Gaeyypa0Jaam4DamaaDaaaleaacaWGSbaabaGaamOuaaaakiaac6ca % caGGUaGaaiOlaiaadEhadaqhaaWcbaGaaGOmaaqaaiaadkfaaaGcca % WG3bWaa0baaSqaaiaaigdaaeaacaWGsbaaaOGaaGjbVlaaysW7caGG % 8bGaaGjbVlaaysW7caWG3bWaaSbaaSqaaiaadMgaaeqaaOGaeyicI4 % SaamitamaaCaaaleqabaGaamOuaaaaaOqaaiabgkziUkaadEhadaah % aaWcbeqaaiaadkfaaaGccqGH9aqpcaWG3bWaa0baaSqaaiaadYgaae % aacaWGsbaaaOGaaiOlaiaac6cacaGGUaGaam4DamaaDaaaleaacaaI % YaaabaGaamOuaaaakiaadEhadaqhaaWcbaGaaGymaaqaaiaadkfaaa % GccaaMe8UaaGjbVlaacYhacaaMe8UaaGjbVlaadEhadaWgaaWcbaGa % amyAaaqabaGccqGHiiIZcaWGmbWaaWbaaSqabeaacaWGsbaaaOGaey % OKH4Qaam4DamaaCaaaleqabaGaamOuaaaakiabg2da9iaadEhadaqh % aaWcbaGaamiBaaqaaiaadkfaaaGccaGGUaGaaiOlaiaac6cacaWG3b % Waa0baaSqaaiaaikdaaeaacaWGsbaaaOGaam4DamaaDaaaleaacaaI % XaaabaGaamOuaaaakiaaysW7caaMe8UaaiiFaiaaysW7caaMe8Uaam % 4DamaaDaaaleaacaWGPbaabaGaamOuaaaakiabgIGiolaadYeacqGH % sgIRcaWG3bWaaWbaaSqabeaacaWGsbaaaOGaeyicI4SaamitamaaCa % aaleqabaGaaiOkaaaaaOqaaiabgkziUkaadEhacqGHiiIZcaGGOaGa % amitamaaCaaaleqabaGaaiOkaaaakiaacMcadaahaaWcbeqaaiaadk % faaaGccqGHsgIRcaGGOaGaamitamaaCaaaleqabaGaamOuaaaakiaa % cMcadaahaaWcbeqaaiaacQcaaaGccqGHgksZcaGGOaGaamitamaaCa % aaleqabaGaaiOkaaaakiaacMcadaahaaWcbeqaaiaadkfaaaGccaaM % e8UaaGjbVlaaysW7caaMe8UaaiikaiaadgeacaGGPaaabaGaeyiaIi % Iaam4DaiabgIGiolaacIcacaWGmbWaaWbaaSqabeaacaGGQaaaaOGa % aiykamaaCaaaleqabaGaamOuaaaakiaacYcacaaMe8UaaGjbVlaays % W7caWG3bWaaWbaaSqabeaacaWGsbaaaOGaeyicI4SaamitamaaCaaa % leqabaGaaiOkaaaakiabgkziUkaadEhadaahaaWcbeqaaiaadkfaaa % GccqGH9aqpcaWG3bWaaSbaaSqaaiaaigdaaeqaaOGaam4DamaaBaaa % leaacaaIYaaabeaakiaac6cacaGGUaGaaiOlaiaadEhadaWgaaWcba % GaamiBaaqabaGccaaMe8UaaGjbVlaacYhacaaMe8UaaGjbVlaadEha % daWgaaWcbaGaamyAaaqabaGccqGHiiIZcaWGmbaabaGaeyOKH4Qaam % 4Daiabg2da9iaacIcacaWG3bWaaSbaaSqaaiaaigdaaeqaaOGaam4D % amaaBaaaleaacaaIYaaabeaakiaac6cacaGGUaGaaiOlaiaadEhada % WgaaWcbaGaamiBaaqabaGccaGGPaWaaWbaaSqabeaacaWGsbaaaOGa % eyypa0Jaam4DamaaDaaaleaacaWGSbaabaGaamOuaaaakiaac6caca % GGUaGaaiOlaiaadEhadaqhaaWcbaGaaGOmaaqaaiaadkfaaaGccaWG % 3bWaa0baaSqaaiaaigdaaeaacaWGsbaaaOGaaGjbVlaaysW7caGG8b % GaaGjbVlaaysW7caWG3bWaaSbaaSqaaiaadMgaaeqaaOGaeyicI4Sa % amitaaqaaiabgkziUkaadEhacqGH9aqpcaWG3bWaa0baaSqaaiaadY % gaaeaacaWGsbaaaOGaaiOlaiaac6cacaGGUaGaam4DamaaDaaaleaa % caaIYaaabaGaamOuaaaakiaadEhadaqhaaWcbaGaaGymaaqaaiaadk % faaaGccaaMe8UaaGjbVlaacYhacaaMe8UaaGjbVlaadEhadaWgaaWc % baGaamyAaaqabaGccqGHiiIZcaWGmbGaeyOKH4Qaam4Daiabg2da9i % aadEhadaqhaaWcbaGaamiBaaqaaiaadkfaaaGccaGGUaGaaiOlaiaa % c6cacaWG3bWaa0baaSqaaiaaikdaaeaacaWGsbaaaOGaam4DamaaDa % aaleaacaaIXaaabaGaamOuaaaakiaaysW7caaMe8UaaiiFaiaaysW7 % caaMe8Uaam4DamaaDaaaleaacaWGPbaabaGaamOuaaaakiabgIGiol % aadYeadaahaaWcbeqaaiaadkfaaaaakeaacqGHsgIRcaWG3bGaeyic % I4SaaiikaiaadYeadaahaaWcbeqaaiaadkfaaaGccaGGPaWaaWbaaS % qabeaacaGGQaaaaOGaeyOKH4QaaiikaiaadYeadaahaaWcbeqaaiaa % cQcaaaGccaGGPaWaaWbaaSqabeaacaWGsbaaaOGaeyOHI0Saaiikai % aadYeadaahaaWcbeqaaiaadkfaaaGccaGGPaWaaWbaaSqabeaacaGG % QaaaaOGaaGjbVlaaysW7caaMe8UaaGjbVlaacIcacaWGcbGaaiykaa % qaaiaacIcacaWGbbGaaiykaiaacYcacaaMe8UaaiikaiaadkeacaGG % PaGaeyOKH46aaiqaaeaafaqabeGabaaabaGaaiikaiaadYeadaahaa % WcbeqaaiaadkfaaaGccaGGPaWaaWbaaSqabeaacaGGQaaaaOGaeyOH % I0SaaiikaiaadYeadaahaaWcbeqaaiaacQcaaaGccaGGPaWaaWbaaS % qabeaacaWGsbaaaaGcbaGaaiikaiaadYeadaahaaWcbeqaaiaacQca % aaGccaGGPaWaaWbaaSqabeaacaWGsbaaaOGaeyOHI0SaaiikaiaadY % eadaahaaWcbeqaaiaadkfaaaGccaGGPaWaaWbaaSqabeaacaGGQaaa % aaaaaOGaay5EaaGaeyOKH4QaaiikaiaadYeadaahaaWcbeqaaiaadk % faaaGccaGGPaWaaWbaaSqabeaacaGGQaaaaOGaeyypa0Jaaiikaiaa % dYeadaahaaWcbeqaaiaacQcaaaGccaGGPaWaaWbaaSqabeaacaWGsb % aaaaaaaa!AAE7! $$