6/93
\begin{frame}{Pushdown Automata}
\begin{goal}{Goal}
A class of automata that accepts the context-free languages.
\end{goal}
\pause\medskip

Nondeterministic finite automata (NFA's):
\begin{itemize}\setlength{\itemsep}{0pt}
\item no memory except for the current state, and
\item has only finitely many states.
\end{itemize}
\pause\medskip

\begin{exampleblock}{}
We need some form of infinite memory to accept languages like
\begin{talign}
\{\,a^nb^n \mid n \ge 0 \,\}
\end{talign}
\end{exampleblock}
\pause\medskip

\begin{goal}{Pushdown automataon}
A pushdown automaton has a \emph{stack} of unlimited size.
\end{goal}
\end{frame}