Timestamps: 0:00 - Intro 1:00 - Main steps in proofs 3:30 - {a^n b^n c^n : n at least 0} 14:20 - {a^i b^j c^k : i at most j, j at most k} 24:00 - {ww : w in {0,1}*} 37:30 - {w in {a,b,c,d}* : w has more c's than a's, b's, or d's}
In the last example, we can pump down either C's or a's If we pump down a's, the resultant string is still in the language Can you please explain this?
This is probably the best explanation I've seen on UA-cam. Most other videos don't make it generalized, they use specific string lengths rather than sticking to general string lengths. Glad I found this simple explanation. Got a sub from me.
Your content and explanation are simply good on a level that cannot be described in words. You make a theoretical material that usually breaks the teeth of computer science students seem so obvious and simple to understand, not to mention beautiful.
Took this material 4 years ago and now for the graduate version of this my professor is giving us a 20% prereq test the second week of class. Great video I'm sure it will improve my grade.
i was reading my notes from my lecture on this topic and had a really tough time understanding it. this cleared things up for me perfectly. thanks sir, youre a life saver.
I really want to thank you because after watching your videos and your explanations, I'm able to explain better all the exercises (I'm assistant professor of theory of computation in Mexico ) 💜💜💜
Thanks for the video, this is one of the clearest explanations I've seen yet. I was having some trouble understanding the exact intuition from my textbook alone.
one thing I struggle with when constructing a proof with pumping lemma is the depth of the explanation you have to go for. At what point does it become obvious enough? for example, at 31:00 he builds an argument about the midpoint shifting, and the first characters of the 2 halves being different from each other. I found it obvious enough that when V and Y are in the same half, pumping it will make that half longer/shorter, and therefore different from the other half. Is my line of thought not good enough?
Great video thank you. A small correction tho, you are saying that in case we only had a language of only ab instead of abc with the pumping lemma we can show that ab is CFL. This is actually false, although it is a CFL, the pumping lemma is not proof that it is (it only works the other way around, it is sound but not complete).
For 0^p1^p0^p1^p why couldn't v be in some partition of the first 0 and 1 and x is in the middle and y be the same length partition of the second 0 and 1 and then u can pump the v and y and get = nums
For the last question's last case where vy will have c's and a's and it is pumped down then c's will be lesser than b's and d's right ? But he mentions c's will be lesser than either b's or d's (because b's and d's are equal) , please clarify.
why doesn't pumping with i=0 work for the first problem? Surely that removes an a from the word making the number of a's less than the number of b's and c's?
I think the tricky part is here to find all cases and prove there's some i that breaks out of the language. on exams, i just don't have enough time to find and write proofs for all of them :(
Yes that's an art, not a science. I wish I could give a specific reason how to do these, but there just isn't a way in general. A good tip is to look at patterns of the strings in the language, and be "right on the edge" of being out of the language, but not there yet, and having the pumping allow yourself to pump out.
For case 1 of the last example wouldn't the number of c's be less than not only the a's, but the b's and d's as well? a, b, and d are all to the power of p. So if we remove at least one p from c, then all of those no longer have a greater number of their respective letter individually, than the number of c's?
23:16 Why cant vxy span a,b and c? Is it correct to state that for any pump length P a span vxy to include a,b,c must have |vxy| >= p+2 (p bs 1 a 1 c) yet |vxy|
I address this in the video. You do need to consider all possible decompositions. If you don't do this, then for some decomposition that you "don't consider", that might be the one that allows w to be pumped and always "stay in" the language.
@@EasyTheory and if even in one case the pumping gives a valid result then will it be considered as CFL ? i mean a^nb^n only becomes CFL when v and y have same number of a and b to be pumped , in rather all the cases it fails to be a CFL . so all the cases must be false for a language to be not CFl , else even if one generates a valid one , then it is CFL. Please tell sir.
For the last example, how do you know that the last case must have at least one occurrence of c? Isn't it possible that v is the empty string and y is all a's? Thanks!
Thank you for your great videos! I have a question: Why do we have to go through EVERY case of w's subdivision? Isn't it enough just to find ONE i, for which we pump out of the language? Cheers, Kasper
Because the lemma states if one language is CFL then exists a pumping length p that satisfies properties. So you go through each case in order to find this p and you wont find any if the language is not CFL
If a language is context free, then does it always satisfy pumping lemma? For example in a^nb^nc^m, m != n it is context free. But if I apply pumping lemma on it, lets say on the string a^pb^pc^(p+1), then it does not satify pumping lemma in some cases. Can anyone shed some light on this? I am confused.
On the 4th language, Case 4, if we have V in the string of C's and Y in the string of A's, and we know that |vy| >0, we could definitely say that V=empty string, so when pumping down to i=0, the number of C's doesnt change, therefore the word stays in the language. Or am I missing something?
I guess because the string is originally decomposed in uvxyz, the number of c's is p+1, so to fit into vxy you can put that +1 c into u (the substring before vxy)
I have a problem in the last example when it could be Cs or As. When we pump down to i=0 we dont know if the Cs will decrease through the V or the As through the Y. If its the As only doesn't this make it valid?
Not only that, it could be that either V or Y have both a C or an A in one of them. If it is the case that VY together has C and A, pump down. No matter what, C cannot be the most frequent character anymore, and we are done. If it was As only, pump up.
In the last question, for the case4, we can think that v is empty and y contains some a's . Then what if we pump down to i=0 ? That concludes that we have more number of c's than a's, b's and d's. and it is actually OK am I wrong?
If v is empty and y contains some a's, then we could just as easily pump up to i=2, which would cause the number of a's to be greater then the number of c's, putting the string outside of the language. He should have mentioned this possible case in his proof, but it still works once you think about it.
Timestamps:
0:00 - Intro
1:00 - Main steps in proofs
3:30 - {a^n b^n c^n : n at least 0}
14:20 - {a^i b^j c^k : i at most j, j at most k}
24:00 - {ww : w in {0,1}*}
37:30 - {w in {a,b,c,d}* : w has more c's than a's, b's, or d's}
In the last example, we can pump down either C's or a's
If we pump down a's, the resultant string is still in the language
Can you please explain this?
@@manikantaalapati7726I think in the case where v is empty and y contains a, in this case we have to pump up instead of pumping down.
Watching this with 7 hrs to go until my theory of computation midterm. You definitely help clear things up, keep it up!
Thanks very much!
@guitarGuy64 how did it go
This is probably the best explanation I've seen on UA-cam. Most other videos don't make it generalized, they use specific string lengths rather than sticking to general string lengths. Glad I found this simple explanation. Got a sub from me.
you really put a lot of work into the channel. nothing but respect for you my friend :)
Thanks
Your content and explanation are simply good on a level that cannot be described in words. You make a theoretical material that usually breaks the teeth of computer science students seem so obvious and simple to understand, not to mention beautiful.
This channel deserves much more, looking at the time and effort you put in the video tysm!
Thank you. I like the writing board and colors you use, it makes it more enjoyable to watch. Your explanations are easy to understand.
Took this material 4 years ago and now for the graduate version of this my professor is giving us a 20% prereq test the second week of class. Great video I'm sure it will improve my grade.
Nicely done. Very interesting topic and I have found it extremely difficult to find a good video on it and this is certainly a great one. Thanks.
i was reading my notes from my lecture on this topic and had a really tough time understanding it. this cleared things up for me perfectly. thanks sir, youre a life saver.
I really want to thank you because after watching your videos and your explanations, I'm able to explain better all the exercises (I'm assistant professor of theory of computation in Mexico ) 💜💜💜
Thanks for the video, this is one of the clearest explanations I've seen yet. I was having some trouble understanding the exact intuition from my textbook alone.
This is such a underrated channel. This needs more views and likes for the type of conent you have, sir! Really amazing stuff!
Thank you so much for this. Perfectly explained, adn you caught every details and edge case and made sure to explain it in simple terms. So grateful!
This is a wonderful video. Both of your pumping lemma examples videos helped me massively.
I struggled to understand this!! My professor could not explain it like that. you just gained one follower
On the last example where you try to pump down c's and a's to make #c's
same question here
Those videos are really helpful, thank you so much :) ! Will you consider making more proofs of context free languages like this one?
It helps clear things up a lot. Thank you so much!
You're welcome!
❤❤❤❤❤❤❤ CS IS LOVE... I BLEED CS
Easily the best Pumping Lemma lecture .... Thank you so much 😇🎉
Crazy good explanation, thanks a lot man
You are literally carrying my master degree
You are the real mvp.
Thanks very much!
So helpful. Thank you so much! Love all your videos!
Thank you so much for the great content! Learning a lot from you. Subbed
Of course, thank you for subbing!
This really clarified things for me, thanks!
Love your videos, my friend is able to self study this subject with them
You really made me understand, nice way of teaching. keep it up
You teach really well!! Thank you!
I had the garbage truck show up on my street at the same time loool. Great video, really helpful!
this was brilliant
youre the goat thank you
helped me a ton with understanding my hw! thank you!
Great to hear!
great video, thank you!
You're welcome!
This is really good thanks
one thing I struggle with when constructing a proof with pumping lemma is the depth of the explanation you have to go for. At what point does it become obvious enough?
for example, at 31:00 he builds an argument about the midpoint shifting, and the first characters of the 2 halves being different from each other. I found it obvious enough that when V and Y are in the same half, pumping it will make that half longer/shorter, and therefore different from the other half. Is my line of thought not good enough?
Great video thank you. A small correction tho, you are saying that in case we only had a language of only ab instead of abc with the pumping lemma we can show that ab is CFL. This is actually false, although it is a CFL, the pumping lemma is not proof that it is (it only works the other way around, it is sound but not complete).
he is GOAT
great content thank you a lot
Pump up the jam, pump it up is a nice song for pumping lemmas xD 43:16
tremendous !!!
I fkn love you man
For 0^p1^p0^p1^p why couldn't v be in some partition of the first 0 and 1 and x is in the middle and y be the same length partition of the second 0 and 1 and then u can pump the v and y and get = nums
For the last question's last case where vy will have c's and a's and it is pumped down then c's will be lesser than b's and d's right ? But he mentions c's will be lesser than either b's or d's (because b's and d's are equal) , please clarify.
why did you put the girl in the thumbnail lmao
why doesn't pumping with i=0 work for the first problem? Surely that removes an a from the word making the number of a's less than the number of b's and c's?
I think the tricky part is here to find all cases and prove there's some i that breaks out of the language.
on exams, i just don't have enough time to find and write proofs for all of them :(
Yes that's an art, not a science. I wish I could give a specific reason how to do these, but there just isn't a way in general. A good tip is to look at patterns of the strings in the language, and be "right on the edge" of being out of the language, but not there yet, and having the pumping allow yourself to pump out.
For case 1 of the last example wouldn't the number of c's be less than not only the a's, but the b's and d's as well? a, b, and d are all to the power of p. So if we remove at least one p from c, then all of those no longer have a greater number of their respective letter individually, than the number of c's?
23:16 Why cant vxy span a,b and c? Is it correct to state that for any pump length P a span vxy to include a,b,c must have |vxy| >= p+2 (p bs 1 a 1 c) yet |vxy|
yes
In the proof, is it necessary to consider all the possible cases or considering just a single one is enough?
I address this in the video. You do need to consider all possible decompositions. If you don't do this, then for some decomposition that you "don't consider", that might be the one that allows w to be pumped and always "stay in" the language.
@@EasyTheory and if even in one case the pumping gives a valid result then will it be considered as CFL ?
i mean a^nb^n only becomes CFL when v and y have same number of a and b to be pumped , in rather all the cases it fails to be a CFL . so all the cases must be false for a language to be not CFl , else even if one generates a valid one , then it is CFL.
Please tell sir.
Could you please solve this? a^k b^j | k>(j-1)^2
struggling buggling juggling tuggling
When you clickbait people into learning
Thnx dude
For the last example, how do you know that the last case must have at least one occurrence of c? Isn't it possible that v is the empty string and y is all a's? Thanks!
if you happen to know the answer of your question, share it pls bcz i have the same question
Thank you for your great videos! I have a question: Why do we have to go through EVERY case of w's subdivision? Isn't it enough just to find ONE i, for which we pump out of the language? Cheers, Kasper
Because the lemma states if one language is CFL then exists a pumping length p that satisfies properties. So you go through each case in order to find this p and you wont find any if the language is not CFL
If a language is context free, then does it always satisfy pumping lemma? For example in a^nb^nc^m, m != n it is context free. But if I apply pumping lemma on it, lets say on the string a^pb^pc^(p+1), then it does not satify pumping lemma in some cases. Can anyone shed some light on this? I am confused.
saving my exam next week :)))
What program are you using to write your problems down?
On the 4th language, Case 4, if we have V in the string of C's and Y in the string of A's, and we know that |vy| >0, we could definitely say that V=empty string, so when pumping down to i=0, the number of C's doesnt change, therefore the word stays in the language. Or am I missing something?
Yes, he missed that case, in that case, you pump up which increases the #a's which becomes more than #c's
@@Uzumaki_Naruto061 this state already was evaulated in case 2, isn't it?
in the last example, in the first case, how can v and y be only in C's. The numbers of C's is p+1 but shouldnt |vxy|
I guess because the string is originally decomposed in uvxyz, the number of c's is p+1, so to fit into vxy you can put that +1 c into u (the substring before vxy)
@@yuricolangelo6688yeah I didn’t think that was possible at the moment but then I realized we could. Thank you
I have a problem in the last example when it could be Cs or As. When we pump down to i=0 we dont know if the Cs will decrease through the V or the As through the Y. If its the As only doesn't this make it valid?
Not only that, it could be that either V or Y have both a C or an A in one of them. If it is the case that VY together has C and A, pump down. No matter what, C cannot be the most frequent character anymore, and we are done.
If it was As only, pump up.
In the last question, for the case4, we can think that v is empty and y contains some a's . Then what if we pump down to i=0 ? That concludes that we have more number of c's than a's, b's and d's. and it is actually OK am I wrong?
If v is empty and y contains some a's, then we could just as easily pump up to i=2, which would cause the number of a's to be greater then the number of c's, putting the string outside of the language.
He should have mentioned this possible case in his proof, but it still works once you think about it.
@@jackmccarthy7644 that falls under case 2
For the first problem, why can't vxy be in both a,b, and c?
I have a similar question regarding the problem 2 {a^i b^j c^k : i at most j, j at most k} . And why we don't consider v and y are all a's and c's?
The reason is that one of the conditions of pumping lemma is that |vxy|
@@sanjeevpenupala ohh tysm hahah the doubt was killing me and finally i get it
BİLEN BİLİR BÜYÜK BAŞKAN HİNDULARA BENZMEEZSIN SANA 302İ GEÇEYİMBİ TEPSİ BAKALVA ALICAM BUYUK USTAD SAYGILAR ABI
Wish I could transfer you my tuition money
My name is Sallie Mae now...
wheres the girl from the thumbnail?
🙄🙄🙄
You’ve earned me my cs degree 🫶🏿
poor w, what did it do to get kicked out of uvxyz?
can u prove that L = {w ∈ {a, b, c}* | (numers of a's and b's are equal and number of c's is greater than number of a's)} is Context-Free ? pls help!