\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 \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}