18/122
\begin{frame}{$L^R$ is Regular}
  There are various possible proofs:
  \pause

  \begin{block}{Construction 1}
    \begin{itemize}
      \item Take an NFA that accepts $L$. 
      \item Reverse all arrows.
      \item Swap final and starting states.
    \end{itemize}
    The resulting automaton accepts $L^R$.
  \end{block}
  \pause
  
  \begin{block}{Construction 2}
    \begin{itemize}
      \item Take a right linear grammar.
      \item Reverse all rules ($x \to y$ becomes $x^R \to y^R$).
    \end{itemize} 
     The result is a left linear grammar for $L^R$. 
  \end{block}
\end{frame}