\begin{frame}{Left Linear Grammars}
  \begin{block}{}
    A grammar $G=(V,T,S,P)$ is \emph{left linear}
    if all production rules are of the form
    \begin{talign}
      A ~\to~ \alert{Bu} 
      \hspace*{1cm} \mbox{or} \hspace*{1cm} 
      A ~\to~ u
    \end{talign}
    with $A,B \in V$ and $u \in T^*$.
  \end{block}
  (Difference with right linear grammars highlighted in \alert{red}.)
  \pause
  
  \begin{block}{Theorem}
    Language $L$ is \emph{regular} \\
    \hfill $\iff$ there is a \emph{left linear grammar} $G$ with $L(G)=L$
  \end{block}
  \pause
  
  \begin{proof}
    \begin{malign}
      \text{$L$ is regular} 
      &\iff \text{$L^R$ is regular}\\
      &\iff \text{right linear grammar for $L^R$}\\
      &\iff \text{left linear grammar for $L$}\\[-2.5ex] 
    \end{malign}
    (For the last step, reverse both sides of all production rules.)
  \end{proof}  
\end{frame}