\begin{frame}{From NFAs to Right Linear Grammars}
  \begin{goal}{}
    For every NFA $M$ there exists a right linear grammar $G$ with
    \begin{talign}
      L(G) = L(M)
    \end{talign}
  \end{goal}
  \pause
  
  \begin{construction}
    Let $M=(Q,\Sigma,\delta,\{q_0\},F)$ be an NFA with a single starting state.
    \pause\medskip
    
    Define $G=(V,T,S,P)$ with $\alert{V = Q}$ and $\alert{T = \Sigma}$ and $\alert{S = q_0}$.
    \pause\medskip
      
    The set \alert{$P$} consists of the following production rules
    \begin{talign}
      \alert{q} &\alert{\to \alpha q'} &&\text{for every $q' \in \delta(q,\alpha)$ where $\alpha \in \Sigma \cup \{\lambda\}$}\\
      %\alert{q} &\alert{\to q'} &&\text{for every $q' \in \delta(q,\lambda)$}\\
      \alert{q} &\alert{\to \lambda} &&\text{for every $q \in F$}
    \end{talign}
    \pause
    Then: $A \Rightarrow^* uB$ in $G$ $\iff$ $A \apath{u} B$ in $M$.
    \pause\medskip
    
    It follows that, \alert{$L(G)=L(M)$}.
  \end{construction}
\end{frame}