\begin{frame}{Right Linear Grammars $\iff$ Regular Languages} \begin{block}{Theorem} Language $L$ is \emph{regular} \\ \hfill $\iff$ there is a \emph{right linear grammar} $G$ with $L(G)=L$ \end{block} \pause\bigskip \begin{proof} The proof consists of two directions: \begin{itemize} \medskip \item $(\Rightarrow)$ Translating NFAs to right linear grammars. \medskip \item $(\Leftarrow)$ Translate right linear grammars to NFAs. \medskip \end{itemize} We have already seen both constructions. \end{proof} \end{frame}