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

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