Pumping Lemma for Context-Free Languages, Statement and FULL PROOF

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.

[@mystic3549]

you have the most professional and intuitive pedagogical style ive ever seen among all profs and teachers teaching theory of computation :) these videos are so interesting ...literally gems ...tysm

[@aerialeye7744]

I swear you're tailoring these perfectly to my ASU professor's lectures lol. Saving my grade!!!!!!!

[@EasyTheory]

Guess where I taught before ;)

[@aerialeye7744]

@@EasyTheory that would make a lot of sense

[@abigarcia9588]

tonight i'm binging on your videos till sunrise bc i have automata theory exam tomorrow, tysm for your vids, best explanations out there! greetings from mexico :)

[@imiriath2411]

howd the exam go? im in the same position...

[@BryanOnofre]

Thank you for this awesome video! very timely because I'm currently taking theory of computation and we are on this subject! Will there be any videos soon on actually using the pumping lemma on a few examples??

[@EasyTheory]

Guess what's coming out on monday ;)

[@hamedpanjeh3947]

Isn't CNF awesome? absolutely yes, Only with your awesome explanation!

[@EasyTheory]

It's so good!

[@instagramlol]

Very clear derivation of pumping lemma thank you

[@korhankemalkaya5231]

Great explanation! Thanks.

[@AyushGupta-mh6vq]

ThNk MadhR jaini

[@heileychan4910]

thank you so much!!

[@isaacchuah7543]

Awesome video. Just wanted to point out that there might be an error at the start when you were talking about the length of the word w. I think (i think anyways) that it should be less than or equal to, not more than or equal to 2^#variables. Ignore me if I'm wrong haha.

[@EasyTheory]

No, it should be greater than, because we want the tree to be super tall, so that a variable repeats. And we can't guarantee that unless we make the string (that we are trying to generate via the parse tree) super long.

[@ngamcode2485]

Thank you a lot.I have a question, what's happening if the parse tree are not fully connected. Does the prove work ?

[@wsverdlik]

Very nice lecture. But a question: in your proof that |vy|>=1 you spoke about productions like A->AB and A->BA and then showed that at least one of v and y could not be empty. But suppose there is a production like A->AA? CNF permits this production, but in fact wouldn't v and y be empty? Thanks.

[@EasyTheory]

Yes that's true. However, note that we looked at a *single* path from the top to the bottom, and so when we reach the "top" A, the path has to pick one of the two variables underneath it, with the other child variable being the "other side".

[@wsverdlik]

@@EasyTheory Ah yes, I see it now. Thank you, very good presentation.

[@gourangpathak4443]

you're a great teacher

[@MoA-fy8bk]

Why do we need to add +1 at the end of 2^(#vars +1) +1?

[@wsverdlik]

Suppose we consider the language (a^n)(b*)(c^n) ; clearly this is context free and the decomposition of vxy would be v=a and y=c. So x is zero or more b's. We know |vxy|

[@razvanefros411]

i hope this reply is useful 2 years later, but to clarify, the value of p is never settled to be something concrete. It is a number that the pumping lemma guarantees to exist if the language is context-free. You can of course think about it and find p for your specific example, but that is redundant, since you already know its Context Free (You can easily create the CFG for this language). Also, be mindful that the Pumping Lemma CANNOT be used to prove a language is Context Free - All CFL are Pumpable, but not all Pumpable Languages are Context Free!! You only really use the number p when trying to prove a language is not context free, in which case you would: I) Assume the language is a CFL (and thus pumpable) II) pick a word from the language with respect to p, making sure its longer than p III) prove that for any way of splitting the picked word into uvxyz it is impossible to pump it, thus achieving contradiction

[@cleopinoli]

Bless you

[@EasyTheory]

No, bless YOU!

[@mustafadogan7958]

Which Programm are u using? Thank you!

[@anastasiamadrevska1668]

Thank you!

[@berkant8074]

amazing! thanks from turkey

[@somesome1315]

Nice lecture. thank you. I have one question. it says |vxy|

[@somesome1315]

Well I thought about it, and is this the reason why existence of pumping lemma doesn't guarantee that it is CNF But all CNF has pumping lemma which means p(it is CNF) -> q(has pumping lemma) but not q -> p

[@drewkavi6327]

goated video

[@nevilholmes5900]

thanks

[@tejaspandit2551]

Does parse tree come under pumping lemma for cfl

[@enochxu9289]

🔥

[@yunni7817]

thank you so much! now I know how it works LOL

[@yoavg2281]

You are the best!😊😊

[@EasyTheory]

Thanks!