效绵鼎 Proof of the Pumping Lemma Start with a CNF grammar for L-{e). Let the grammar have m variables. Pick n=2m. Let z,of length >n,be in L. We claim(“Lemma 1”)that a parse tree with yield z must have a path of length m+2 or more. .5Proof of the Pumping Lemma ◼ Start with a CNF grammar for L – {ε}. ◼ Let the grammar have m variables. ◼ Pick n = 2m. ◼ Let z, of length > n, be in L. ◼ We claim (“Lemma 1 ”) that a parse tree with yield z must have a path of length m+2 or more. 5