\begin{frame}{Regular Languages: Reversal}
  \begin{block}{Theorem}
    If $L$ is regular, then its reverse \alert{$L^R$} is regular.
  \end{block}
  \pause
  
  \begin{block}{Construction}
    Let $L$ be a regular language.
    \pause\medskip
    
    Then there is an NFA $M = (Q,\Sigma,\delta,S,F)$ with $L(M) = L$.
    \pause\medskip

    Let $N$ be the NFA obtained from $M$ by
    \begin{itemize}
    \pause
      \item reversing all arrows (transitions),
    \pause
      \item exchanging starting states $S$ and final states $F$.
    \end{itemize}
    \pause
    Then we have
    \begin{talign}
      q \apath{w} q' \text{ in $M$} \;\;\iff\;\;
      q' \apath{w^R} q \text{ in $N$}
    \end{talign}
    \pause
    Since starting and final states are swapped, it follows that
    \begin{talign}
      w \in L(M) \iff w^R \in L(N)
    \end{talign}
  \end{block}
\end{frame}