\begin{frame}{From NPDA's to Context-Free Grammars}
  \begin{construction}
    Let $M=(Q,\Sigma,\Gamma,\delta,q_0,z,F)$ be an NPDA.
    \pause
    Transform $M$ s.t.
    \medskip
    
    \emph{Assumption}: $F=\{\,q_f\,\}$ and $q_f$ reachable only with empty stack.\\
    \pause\medskip

    We define a context-free grammar $(V,T,S,P)$ as follows:
    \begin{talign}
      T &= \Sigma &
      V &= \{\, (q\,b\,q') \mid q,q'\in Q,b \in \Gamma \,\} &
      S &=(q_0\,z\,q_f)
    \end{talign}
    \emph{Intuition}: $(q\,b\,q') \Rightarrow^+ w \iff (q,w,b)\vdash^+(q',\lambda,\lambda)$.
    \pause\medskip

    The set $P$ contains the following rules:
    \begin{itemize}\setlength{\itemsep}{0pt}
      \item 
        If $q \stackrel{\alpha[b/\lambda]}{\longrightarrow} q'$, then\\ % $(q',\lambda)\in\delta(q,\alpha,b)$, then\\
        \alert{$(q\,b\,q') \to \alpha$} in $P$.
      \item 
        If $q \stackrel{\alpha[b/c_1\cdots c_n]}{\longrightarrow} q'$ with $n\geq 1$, then\\ %$(q',c_1\cdots c_n)\in\delta(q,\alpha,b)$
        \alert{$(q\,b\,r_n) \to \alpha\,(q'\,c_1\,r_1)\,(r_1\,c_2\,r_2)\cdots(r_{n-1}\,c_n\,r_n)$}  in $P$\\
        for \emph{all} $r_1,\ldots,r_n \in Q$
    \end{itemize}
    \pause
    Then we have $L(G)=L(M)$.
  \end{construction}
\end{frame}