120/122

\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}