Automata & Formal Languages · Instrument 03 · Pushdown Automata

One stack changes everything

A finite automaton can't count, so it can't match aⁿbⁿ or balanced brackets. Add a single stack — push, pop, peek the top — and it can. These are the context-free languages: the grammars behind programming languages, and the machines that parse them.

PDA

Grammar derivation

Parse tree

Grammar ↔ PDA

Pushdown automaton

Build a string

The stack is the only unbounded memory, and only the top is visible. For aⁿbⁿ: push an A for each a, then pop one per b — empty exactly when the counts match. Accept when input is consumed and the stack is empty.

PDA

Grammar

Target string

A leftmost derivation rewrites the leftmost nonterminal at each step using a production, until only terminals remain. The sequence of sentential forms is a proof that the string is in the language.

derivation

Arithmetic grammar

E → E + T | T
T → T * F | F
F → ( E ) | id

Expression

The parse tree's shape encodes meaning: because * lives below + in the grammar, multiplication sits deeper in the tree and binds tighter. The structure is the precedence.

parse tree

Top-down PDA from grammar

Target string

Any grammar becomes a PDA: push the start symbol, then predict (replace a nonterminal on top by a production's right side) or match (pop a terminal that equals the next input). The stack always holds the rest of the sentential form.

grammar as PDA