13/93
\begin{frame}{Pushdown Automata}
  Next to the input alphabet $\Sigma$, there is now a \emph{stack alphabet} $\Gamma$.
  \pause\medskip
  
  \begin{block}{}
    A \emph{stack} is a finite sequence of elements from $\Gamma$.
    \pause\medskip
    
    Elements can be added or removed only on the top of the stack.
  \end{block}
  \pause\medskip
  
  \begin{goal}{}
    A transition reads the topmost element of the stack
    \begin{talign}
      \delta : Q \times (\Sigma \cup \{ \lambda \}) \times \alert{\Gamma} \to \ldots
    \end{talign}
    \pause
    and exchanges it with zero or more new elements:
    \begin{talign}
      \delta : Q \times (\Sigma \cup \{ \lambda \}) \times \Gamma \to 2^{Q \times \alert{\Gamma^*}}
    \end{talign}
    \pause
    The nondeterministic choice $\delta(q,\alpha,b)$ must always be \alert{finite}!
  \end{goal}
  \pause\medskip
  
  \begin{block}{}
    Initially, stack contains one symbol: \emph{stack start symbol} $z \in \Gamma$.
  \end{block}
  \bigskip
\end{frame}