Pushdown automata

We will now consider a new notion of automata *pushdown
automata* (PDA). PDAs are finite automatons with a stack, i.e. a
data structure which can be used to store an arbitrary number of
symbols (hence PDAs have an infinite set of states) but which
can be only accessed in a *last-in-first-out* (LIFO) fashion.
The languages which can be recognized by PDA are precisely the context
free languages.

- What is a pushdown automaton?
- How does a PDA work?
- The language of a PDA
- Deterministic PDAs
- Context free grammars and push-down-automata

Thorsten Altenkirch 2001-05-08