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}