19/122
\begin{frame}{$L^R$ is Regular}
  \begin{block}{Construction 3}
    Reverse a regular expression (defined by recursion):
    \begin{talign}
      \begin{array}{lcl}
        {\it rev}(\emptyset) &=& \alert{\emptyset} \\
        {\it rev}(\lambda) &=& \alert{\lambda} \\
        {\it rev}(a) &=& \alert{a} \hspace*{3cm} (a \in \Sigma) \\
        {\it rev}(r_1 + r_2) &=& \alert{{\it rev}(r_1) + {\it rev}(r_2)} \\
        {\it rev}(r_1 \cdot r_2) &=& \alert{{\it rev}(r_2) \cdot {\it rev}(r_1)} \\
        {\it rev}(r^*) &=& \alert{{\it rev}(r)^*}
      \end{array}
    \end{talign}
    Using induction, it can be shown that
    \begin{talign}
      \alert{L({\it rev}(r)) ~=~ L(r)^R}
    \end{talign}
  \end{block}
\end{frame}