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