Why pushdown automata

• pushdown automata are like finite automata, but also work with stack
• 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 correspond to efficient one-pass parsing algorithms

• typically sufficient for parsing programming languages

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

There are more general deterministic pushdown automata

• one example are LR(1) parsers