\begin{frame}{Language Accepted by a Pushdown Automaton}
  A \emph{configuration} $(q,w,u)$ of an  NPDA consists of:
  \smallskip
  \begin{itemize}\setlength{\itemsep}{0pt}
  \item current state \alert{$q \in Q$}
  \item input word \alert{$w \in \Sigma^*$}
  \item current stack \alert{$u \in \Gamma^*$}
  \end{itemize}
  \pause\medskip
  
  \begin{goal}{}
    The \emph{step relation} on configurations is defined by
    \begin{talign}
      (q,\, \alpha w,\, bu) \vdash (q',\, w,\, vu)
    \end{talign}
    whenever $(q',v) \in \delta(q,\alpha,b)$.
  \end{goal}
  We write $\vdash^*$ for computation (zero or more steps).
  \pause\medskip

  \begin{block}{}
    The \emph{language generated by} NPDA 
    $M=(Q,\Sigma,\Gamma,\delta,q_0,z,F)$ is
    \begin{talign}
      L(M) = \{\, w \in \Sigma^* \mid (q_0,w,z) \vdash^* (q',\lambda,u) \text{ where } q' \in F \,\}.
    \end{talign}
  \end{block}  
  Note: no condition on the stack $u$ at the end.
  \bigskip
\end{frame}