\begin{frame}{Left Linear Grammars}
    A grammar $G=(V,T,S,P)$ is \emph{left linear}
    if all production rules are of the form
      A ~\to~ \alert{Bu} 
      \hspace*{1cm} \mbox{or} \hspace*{1cm} 
      A ~\to~ u
    with $A,B \in V$ and $u \in T^*$.
  (Difference with right linear grammars highlighted in \alert{red}.)
    Language $L$ is \emph{regular} \\
    \hfill $\iff$ there is a \emph{left linear grammar} $G$ with $L(G)=L$
      \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] 
    (For the last step, reverse both sides of all production rules.)