Prove that $(L^R)^* = (L^*)^R$ for all languages L 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 ? 
 A: 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$.
A: $$\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!
$$
