• Overview
• Details
• Exercises

Context-free grammars (CFGs) generate languages via productions; pushdown automata (PDAs) recognize the same class using a stack. Normal forms and parsing algorithms enable efficient recognition and syntax analysis.

• CFG: G = (V, Σ, R, S); derivations, parse trees, ambiguity; leftmost/rightmost derivations.
• Normal forms: Chomsky Normal Form (CNF), Greibach Normal Form (GNF); ε-, unit-, useless-production elimination.
• PDAs: (Q, Σ, Γ, δ, q₀, Z₀, F); acceptance by final state or empty stack; equivalence to CFGs.
• Parsing: CYK algorithm (O(n^3) in CNF); LL/LR parsing overview; closure and decision properties.
• Closure limits: CFLs closed under union, concat, star; not under intersection/complement; pumping lemma for CFLs.

1. Given L = { a^n b^n | n ≥ 0 }, provide a CFG and an equivalent PDA (informally described).
2. Convert a CFG to CNF by eliminating ε- and unit-productions; then run one CYK table for a short string.
3. Give an ambiguous grammar for arithmetic expressions and a corresponding unambiguous grammar using precedence/associativity.