\begin{frame}{Language Accepted by a Pushdown Automaton}
  When a NPDA reads a words, we need to keep track of:
  \item the current state \alert{$q \in Q$}
  \item the remaining input \alert{$w \in \Sigma^*$}
  \item the current stack \alert{$u \in \Gamma^*$}
    If $(q',v) \in \delta(q,\alpha,b)$, this means that 
      \item from state \alert{$q$} with input \alert{$\alpha w$} and stack $\alert{b}u$ 
    the automaton can do a transition to 
      \item state \alert{$q'$} with input \alert{$w$} and stack $\alert{v}u$.
    This is denoted by
    \quad $\alert{(q,\, \alpha w,\, bu) \vdash (q',\, w,\, vu)}$.

    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. It is often empty.