Theory of Computation · ODD 2026 · Context-Free Languages & PDAs

Context-Free Languages

How grammars, normal forms, and pushdown automata relate — for orientation and review, not first-time reading. Pair this with the lecture notes for the “why,” and the flashcards for recall.

Context-Free Languages Grammars in Action Simplifying Grammars Normal Forms Pushdown Automata Proving Non-CF-ness Derivation ⇒* Parse tree & yield Leftmost / rightmost Ambiguity Useless symbols ε-productions Unit productions Safe order Chomsky Normal Form CYK, O(n³) Greibach Normal Form ε-free PDA Stack push / pop 6-tuple PDA Configuration, ⊢ DPDA ⊊ PDA Pumping lemma (CFL) Repeated variable uvxyz split {ww} vs {ww^R}
How context-free grammars, their normal forms, and pushdown automata relate: a grammar generates via derivation, gets simplified and reshaped into a normal form for a specific algorithm, that form drives a matching PDA construction, and the pumping lemma is the one tool for proving a language escapes the class entirely.
Grammars in Action Simplifying Grammars Normal Forms Pushdown Automata Proving Non-CF-ness
AI-generated study aid. This mind map was generated with AI assistance and has been reviewed, but it may still contain small errors. If you spot one, please report it so it can be corrected.