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

\subsection{Left Linear Grammars}

\themex{Left Linear Grammars}