Lecture 8 - Context-Free Grammars and Pushdown Automata
(Skeleton for Fall 2026.)
Context-Free Grammars
TODO: rules, derivations, parse trees, ambiguity; CFGs in the wild (programming language syntax).
Pushdown Automata
TODO: adding a stack to an NFA; formal definition; equivalence with CFGs (statement, proof sketch only).
Limits of Context-Free Languages
TODO: the CFL pumping lemma (statement); 0^n 1^n 2^n is not context-free.
The Chomsky Hierarchy
TODO: regular inside context-free inside decidable inside recognizable; the hierarchy as the map of the whole course, each fence crossed by a machine upgrade.