Pushdown automata are like finite automata, but also work with stack

• next state is given by:
  • current state
  • current input symbol read
  • top of the stack
• within each step the automaton can pop a symbol or push a symbol onto stack

We have seen a pushdown automaton for top-down parsing in Interpreting LL Parsing Table

Why pushdown automata?

• parsing requires stack

Equivalence of expressive power:

Non-deterministic and deterministic finite state automata are equally expressive

Non-deterministic pushdown automata are more expressive than non-deterministic ones

• we cannot determinize pushdown automata in general

Deterministic automata can be used to construct efficient one-pass parsing algorithms

• typically sufficient for parsing programming languages
• for parsing mathematical formulas and natural languages, general grammars are more suitable (Earley Parser)