Lecture 8 (Computation Theory) Pumping Lemma, Right Linear Grammars, and Context-Free Grammars

The pumping lemma is used to prove that:

1. A.A given language is regular by exhibiting a pumping length
2. B.Two DFAs recognize exactly the same language
3. C.A given language is NOT a regular language
4. D.Every context-free grammar is unambiguous