\begin{frame}{From Right Linear Grammars to NFAs}
  
  \begin{goal}{}
    For every right linear grammar $G$ there exists an NFA $M$ with
    \begin{talign}
      L(M) = L(G)
    \end{talign}
  \end{goal}
  \pause

  \begin{construction}[$\Leftarrow$]
    Let $G=(V,T,S,P)$ be a right linear grammar.
    \pause\medskip
    
    Make $G$ to \alert{strictly} right linear.
    Then all rules are of the form
    \begin{talign}
    \alert{A \to u} \quad\text{or}\quad \alert{A \to uB}
    \end{talign}
    for $A,B \in V$, $u \in (T\cup \{\lambda\})$.
    \pause
    Let NFA $M=(Q,\Sigma,\delta,\alert{\{\,S\,\}},F)$ with 
    \begin{talign}
      \alert{\Sigma = T} && \alert{Q = V \cup \{\,\Omega\,\}} && \alert{F = \{\,\Omega\,\}}
    \end{talign}
    where $\Omega \not\in V$.
    \pause
    The transitions $\alert{\delta}$ are given by
    \begin{talign}
      A &\stackrel{u}{\to} B &&\text{for every $A \to uB$ in $G$}\\[-1mm]
      A &\stackrel{u}{\to} \Omega &&\text{for every $A \to u$ in $G$}
    \end{talign}
    \pause
    Then $S \Rightarrow^*w \in T^*$
    $\iff$ $M$ accepts $w$.
    \pause
    Hence $L(G) = L(M)$.
  \end{construction}
\end{frame}