Lecture 11 (Computation Theory) Pumping Lemma, Non-Context-Free Languages, and Review

The pumping lemma for context-free languages is used in practice almost exclusively to:

1. A.Construct a PDA for a given context-free grammar
2. B.Convert a CFG into Chomsky normal form
3. C.Show that a given language is NOT context-free
4. D.Show that two context-free grammars generate the same language