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
FINALLY got to understand the pumping lemma!!! YOU ARE AMAZING! THANK YOU SO MUCH! Very intuitive video, easy to follow and understand an d better than all the slides, notes, and textbook readings I've interacted with so far. Thank you!!!
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 :)
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??
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.
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.
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.
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".
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|
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
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
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
I swear you're tailoring these perfectly to my ASU professor's lectures lol. Saving my grade!!!!!!!
Guess where I taught before ;)
@@EasyTheory that would make a lot of sense
FINALLY got to understand the pumping lemma!!! YOU ARE AMAZING! THANK YOU SO MUCH! Very intuitive video, easy to follow and understand an d better than all the slides, notes, and textbook readings I've interacted with so far. Thank you!!!
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 :)
howd the exam go? im in the same position...
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??
Guess what's coming out on monday ;)
Isn't CNF awesome? absolutely yes, Only with your awesome explanation!
It's so good!
Great explanation! Thanks.
you're a great teacher
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.
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.
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.
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".
@@EasyTheory Ah yes, I see it now. Thank you, very good presentation.
Thank you a lot.I have a question, what's happening if the parse tree are not fully connected. Does the prove work ?
Why do we need to add +1 at the end of 2^(#vars +1) +1?
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|
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
ThNk MadhR jaini
Which Programm are u using? Thank you!
amazing! thanks from turkey
Does parse tree come under pumping lemma for cfl
Nice lecture. thank you.
I have one question. it says |vxy|
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
thank you so much!!
Thank you!
You are the best!😊😊
Thanks!
Bless you
No, bless YOU!
thanks
love it
goated video
Very clear derivation of pumping lemma thank you
thank you so much! now I know how it works LOL
🔥