Here we prove (and state) the pumping lemma for context-free languages (CFL), by observing a parse tree of a CFG in Chomsky Normal Form (CNF). The properties of the parse tree allow us to show that if the string generated is big enough, the longest root-to-leaf path in the parse tree must repeat a variable. We utilize this fact to generate more parse trees (i.e., more strings the CFG makes), and look at the properties of parts of this string.

If you like this content, please consider subscribing to my channel:    / @easytheory  

▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.