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}