Showing that all regular languages are closed under reversal I'm trying to show that $L^{reverse} = \{w^{reverse}:w \in L\}$ is a regular language. The first argument I can come up with is simply: if we have an NFA for $L$, then an NFA for $L^{reverse}$ can be constructed by switching all final states to initial states and all initial states to final states. However, I'm not trying to prove that $L^{reverse}$ is regular by using regular expressions. If we have some regular expression for a language, is there some universal way we can show that the regular expression can be reversed to give $L^{reverse}$ which is regular?
 A: Hint:


*

*Regular expressions are defined as 

*

*a few basic atoms ($\varnothing$, $\{\varepsilon\}$, $\{\alpha\}$ for any letter $\alpha \in \Sigma$),

*some operators (concatenation, sum, Kleene star),

*sometimes some redundancy (complement, intersection).


*Atoms do not need reversing and any of the operators could be flipped, i.e. you could define function $R$ that would reverse your expression, e.g. $R[\![A\cdot B]\!] = R[\![B]\!] \cdot R[\![A]\!]$.

*Then, you could prove inductively (with respect to expression-tree) that $R$ indeed generates an expression for reversed language.


I hope this helps $\ddot\smile$
Edit: To long for a comment. To reverse an expression go step-by-step, for example
\begin{align}
R\Bigg[\!\!\Bigg[\Big(\big((0\cdot0)^∗\cdot(1\cdot1)\big)∪(0\cdot1)\Big)^∗\Bigg]\!\!\Bigg] &= \Bigg(R\Big[\!\!\Big[\big((0\cdot0)^∗\cdot(1\cdot1)\big)∪(0\cdot1)\Big]\!\!\Big]\Bigg)^* \\
R\Big[\!\!\Big[\big((0\cdot0)^∗\cdot(1\cdot1)\big)∪(0\cdot1)\Big]\!\!\Big] &= R\Big[\!\!\Big[(0\cdot0)^∗\cdot(1\cdot1)\Big]\!\!\Big] \cup R[\![0\cdot1]\!] \\
R\Big[\!\!\Big[(0\cdot0)^∗\cdot(1\cdot1)\Big]\!\!\Big] &=
R[\![1\cdot1]\!]\cdot R[\![(0\cdot0)^*]\!] = (1\cdot1) \cdot (0\cdot0)^*\\
R[\![0\cdot1]\!] &= R[\![1]\!] \cdot R[\![0]\!] = 1\cdot 0
\end{align}
so you finally get
$$ R\Bigg[\!\!\Bigg[\Big(\big((0\cdot0)^∗\cdot(1\cdot1)\big)∪(0\cdot1)\Big)^∗\Bigg]\!\!\Bigg] = \Big(\big((11)(00)^*\big)\cup(10)\Big)^*.$$
