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 RUclips. 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.
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 ) 💜💜💜
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.
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.
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).
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
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 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.
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?
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 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
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?
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 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.
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 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)
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 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
you really put a lot of work into the channel. nothing but respect for you my friend :)
Thanks
This is probably the best explanation I've seen on RUclips. 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.
This channel deserves much more, looking at the time and effort you put in the video tysm!
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 ) 💜💜💜
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.
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.
This is such a underrated channel. This needs more views and likes for the type of conent you have, sir! Really amazing stuff!
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.
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.
Easily the best Pumping Lemma lecture .... Thank you so much 😇🎉
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!
Crazy good explanation, thanks a lot man
❤❤❤❤❤❤❤ CS IS LOVE... I BLEED CS
On the last example where you try to pump down c's and a's to make #c's
same question here
This really clarified things for me, thanks!
So helpful. Thank you so much! Love all your videos!
You are the real mvp.
Thanks very much!
Thank you so much for the great content! Learning a lot from you. Subbed
Of course, thank you for subbing!
You really made me understand, nice way of teaching. keep it up
Love your videos, my friend is able to self study this subject with them
I had the garbage truck show up on my street at the same time loool. Great video, really helpful!
You teach really well!! Thank you!
youre the goat thank you
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).
helped me a ton with understanding my hw! thank you!
Great to hear!
this was brilliant
great video, thank you!
You're welcome!
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
This is really good thanks
I fkn love you man
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
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?
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.
tremendous !!!
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?
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 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
Could you please solve this? a^k b^j | k>(j-1)^2
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?
saving my exam next week :)))
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
struggling buggling juggling tuggling
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.
What program are you using to write your problems down?
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
Thnx dude
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
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?
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
why did you put the girl in the thumbnail lmao
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
When you clickbait people into learning
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
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!