next up previous
Next: What is a pushdown Up: Machines and their languages Previous: Ambiguity

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.


Thorsten Altenkirch 2001-05-08