Showing that all regular languages are closed under reversal

Question

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?

Answer 1

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