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

  \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. It is often empty.
  \bigskip
\end{frame}