In case anybody is wondering about the pumping length, you don't have to specify the length. Simply say that there some pumping length 'p' that would result in too many of one letter, wrong pattern, ect. You could, for example, say that v is made of all a's and y is made of all b's, logically if you were to pump by any 'p' then you would have too many letters of either type because you're using 'i' for the check. 'i' is the important one, and you could select any 'i' that works. I hope this helped
I agree. Naively if you only use a specific example where you specify p, your professor will 100% mark you off, because that is not the general case! I got points off from my homework for mentioning a length in my proof. Just avoid it entirely! This is very very important for exams. Reading the pumping lemma, it basically means, if there exists A p, which can be a known number, that satisfies the conditions, the string can be pumped; the reverse is NOT true. You cannot use a string and p = 7 that fails to satisfy the pumping lemma to reject that there MIGHT be a p out of ALL the other p's you didn't explore that makes the string belong to A. That's why you should only use a general p in your proof. I think this video should be updated.
A better way to think about it is that you are given a p greater than one. Thinking in ways of playing a game with an adversary is very useful when doing proofs.
I might be wrong but I think case 1 is false; When you split your word into uvxyz it turns out that |vxy|>P because v= aa, x = abbbbc and y = c, this means that |vxy| = 9 and p = 4 This contradicts rule 2 of the PL which states that |vxy|
In case your still wondering your absolutely right. His counter example is invalid as the pumping lemma wouldn’t apply to it. In fact picking any value of p is invalid. These proofs should be done generally
both examples are wrong. The pumping lemma states that |vxy| p = 4. furthermore you have to show that no matter how you divide your string the three conditions of the pumping lemma cant be satisfied all at once, so you have to show all or pick your cases in a more general way so it is clear that no matter how you divide it, it will always come do a contradiction
@@KayDee_88 It doesn't meet that condition in the case that he took. But Pumping lemma states that for some uvxyz the condition is valid, not for ALL uvxyz. So, disproving for one case is not sufficient. You need to disprove for all cases and say that there exists NO uvxyz such that this condition is true. His proofs are wrong and incomplete.
So we have to choose the string division which meets the condition |vxy|≤p&|vy|>0 ,so that we can prove the first condition is wrong ,that way we can generalise for different strings divided in different ways
Attention!! please at 3:57 you take out vxy from the 'S' right? but, according to pumping lemma, the way I choose vxy is that the "length of vxy is at most p" i,e, vxy
Thank you so much! I can't express how much you just helped me. It's almost 4am and I was just completely lost on this subject, I was struggling to understand how abc would be expressed as uvxyz and none of the sources that I checked explained it, they just assumed I would know. I finally understand it. Thank you so much!!!!!
Thank you, great explanation. Favorite so far and most recommended... Stays textbookual, yet very direct unlike a textbook. I appreciate it, hopefully do well on test and great to know
Sir just one thing. From that video where you explained the pumping lemma for regular language and took p as 7, that's not right. I did the same In my internals and professor reduced the marks In that question.. He said, "You cannot assume a P. You have to work out with p as a variable only".
Late to the party but as others have eluded to: proof by contradiction using a counter example is the same thing as trying to prove the language isn't context free because you can't find a string that that an NPDA would accept. This is a fallacy.
This is conpletely wrong, as others have pointed out. You are given an n greater than 1. Then you can choose a word that's as long as or longer than n. Then you have to show FOR ALL POSSIBLE decompositions that satisfy the two conditions (vwx is shorter or as long as n; and v and x are not both empty) that the word can be pumped out of the language.
7:17 Wrong. The pumping lemma says *there exists* a split uvxyz such that those conditions are satisfied; it doesn't say it should be satisfied for all splits, so saying that it is not context free just because it doesn't belong for only case 1 is incorrect
I have observed that in answering your questions on pumping lemma you always chose value of p to be same as value of n. In this particular case p=4 and n=4. You did same for pumping lemma examples for regular languages when you had to prove that a pow(n) b pow(n) was not a regular language. Any specific reason? Thank you.
Do not follow this method. Method of contradiction only works if the statement claims to be true for "all" values of p, not when it says "there exists" a value of p. In this case, you have to show that no value of p exists that satisfies these conditions by assuming a general p and proceeding to disprove the language.
I don't think this is correct. You need to show that all the possible decompositions of S, THAT SATISFY the other 2 conditions, can be pumped out of the language.
Straight incorrect solution, you cannot specify p value. you have proved the string with that p value does not satisfy pumping lemma, instead you should take a generic string say a^p b^p and prove that for any split and i>=0 the string will not belong to L.
Is it necessary to do more than 1 case doing a pumping lemma contradiction proof for context free languages? All the examples I see online prove with at least 2 or more cases, but no one actually explains why. Is it sufficient to disprove with 1 case?
I think thats wrong ... The reason multiple cases are used is because you have to show, that NOT A SINGLE uvxyz decomposition exists, such that all three conditions are satisfied. To give a counter example to Nesos Answer: L = {a^nb^n} is a context-free language. However if you choose v such that it contains as and bs, condition 1 will not be satisfied. However, that doesnt mean that L is not context-free.
Werbung Schrott it took me 16 hours to get this conjecture. And you have confirmed my guess. Thank you. I hate teacher/professor that doesn't teach properly!!
No. The Pumping Lemma says that there EXISTS a decomposition with the attributes. So you have to show that every single possible case is not in the language after being pumped.
![[#2024MAMA] BIGBANG (빅뱅) - 뱅뱅뱅 (BANG BANG BANG) + FANTASTIC BABY | Mnet 241123 방송](http://i.ytimg.com/vi/EQsYfiPR9uM/mqdefault.jpg)
kudos to students from ktu.. you are not the only "one"....
Ktu 2024
In case anybody is wondering about the pumping length, you don't have to specify the length. Simply say that there some pumping length 'p' that would result in too many of one letter, wrong pattern, ect. You could, for example, say that v is made of all a's and y is made of all b's, logically if you were to pump by any 'p' then you would have too many letters of either type because you're using 'i' for the check. 'i' is the important one, and you could select any 'i' that works. I hope this helped
I agree. Naively if you only use a specific example where you specify p, your professor will 100% mark you off, because that is not the general case! I got points off from my homework for mentioning a length in my proof. Just avoid it entirely! This is very very important for exams. Reading the pumping lemma, it basically means, if there exists A p, which can be a known number, that satisfies the conditions, the string can be pumped; the reverse is NOT true. You cannot use a string and p = 7 that fails to satisfy the pumping lemma to reject that there MIGHT be a p out of ALL the other p's you didn't explore that makes the string belong to A. That's why you should only use a general p in your proof. I think this video should be updated.
A better way to think about it is that you are given a p greater than one.
Thinking in ways of playing a game with an adversary is very useful when doing proofs.
I might be wrong but I think case 1 is false;
When you split your word into uvxyz it turns out that |vxy|>P because v= aa, x = abbbbc and y = c, this means that |vxy| = 9 and p = 4
This contradicts rule 2 of the PL which states that |vxy|
same thing here! it's confusing me
In case your still wondering your absolutely right. His counter example is invalid as the pumping lemma wouldn’t apply to it. In fact picking any value of p is invalid. These proofs should be done generally
suffering from the same doubt
Yes, this is true, what we do have in fact is case where v and y have a and b/ b and c as examples of case 1
Yes the proof is wrong, see the next example he has changed the approach
both examples are wrong. The pumping lemma states that |vxy| p = 4. furthermore you have to show that no matter how you divide your string the three conditions of the pumping lemma cant be satisfied all at once, so you have to show all or pick your cases in a more general way so it is clear that no matter how you divide it, it will always come do a contradiction
but doesn't that mean the 3rd condition isn't met and hence A ain't CFL as we previously assumed??
@@KayDee_88 It doesn't meet that condition in the case that he took. But Pumping lemma states that for some uvxyz the condition is valid, not for ALL uvxyz. So, disproving for one case is not sufficient. You need to disprove for all cases and say that there exists NO uvxyz such that this condition is true. His proofs are wrong and incomplete.
So we have to choose the string division which meets the condition
|vxy|≤p&|vy|>0 ,so that we can prove the first condition is wrong ,that way we can generalise for different strings divided in different ways
Attention!! please at 3:57
you take out vxy from the 'S' right?
but, according to pumping lemma, the way I choose vxy is that the "length of vxy is at most p" i,e, vxy
2:39 I think he says that we are only going to concentrate on condition 1
That is the reason why i went back to comments...
+1 should be should be |vxy|
holy cow I dont know how you made me understand that in just 12 minutes. I was struggling with this too much
Thank you so much! I can't express how much you just helped me. It's almost 4am and I was just completely lost on this subject, I was struggling to understand how abc would be expressed as uvxyz and none of the sources that I checked explained it, they just assumed I would know. I finally understand it. Thank you so much!!!!!
Thank you, great explanation. Favorite so far and most recommended... Stays textbookual, yet very direct unlike a textbook. I appreciate it, hopefully do well on test and great to know
Sir just one thing. From that video where you explained the pumping lemma for regular language and took p as 7, that's not right. I did the same In my internals and professor reduced the marks In that question.. He said, "You cannot assume a P. You have to work out with p as a variable only".
he's explaining the concept only by taking p = some value, but while you are proving you have to generalise.
the | vxy | length have to be smaller or equal to p
L={a^i b^j c^k l I
Your case 1 is invalid. |vxy| is greater than your pumping length 4.
index: it is also called Bar-Hillel Lemma
your both cases are wrong , |vxy| should be less than or equal to 'p' .
yes u r ryt!
Late to the party but as others have eluded to: proof by contradiction using a counter example is the same thing as trying to prove the language isn't context free because you can't find a string that that an NPDA would accept. This is a fallacy.
This is conpletely wrong, as others have pointed out.
You are given an n greater than 1.
Then you can choose a word that's as long as or longer than n.
Then you have to show FOR ALL POSSIBLE decompositions that satisfy the two conditions (vwx is shorter or as long as n; and v and x are not both empty) that the word can be pumped out of the language.
your pace is awesome.
7:17 Wrong. The pumping lemma says *there exists* a split uvxyz such that those conditions are satisfied; it doesn't say it should be satisfied for all splits, so saying that it is not context free just because it doesn't belong for only case 1 is incorrect
Incorrect division of string in Case 1. The string was supposed to be divided into uvxyz in such a way that | vxy |
How do you just choose P? Doesn't it say ∃P ?
Thankyou sir
well explained
Thanks!
I have observed that in answering your questions on pumping lemma you always chose value of p to be same as value of n. In this particular case p=4 and n=4. You did same for pumping lemma examples for regular languages when you had to prove that a pow(n) b pow(n) was not a regular language. Any specific reason? Thank you.
that's what i have been searching for why this specifically ?
brilliantly explained
Done - thanks
Sen nasil bi kralsin ya ..
dogrusun
Incorrect. There is a rule that the length of vxy must be less than or equal to p.
So according to this a^n b^n is also not a CFL
The same question is on Wikipedia. Yiu can check it out to solve it the correct way.
Any one case is enough for exam right?? 👀
Pls upload other videos push down Automata, Turing machine..
I am confused while testing you having taken |vxy|>=p which contradicts your previous lecture's steps.
PERFECT!
Awesome
Sir plz upload electromagnetics for ece lectures...
you have totally messed it up, sir!! I came here for simplification , but huhhhhhhhhhhhhh :XD
You the goat
How did he actually categorize some a's for v some for v and some for x and y,z respectively??Lyk how we actually take that quantity??
It is not correct to take a particular value of the pumping length. One needs to prove for all possible pumping length.
if we put i= 1 in case 1 then what should we get ?
If S>P then how you have taken P=4 ??
What is the difference between pumping lema for non regular and pumping lema for context free?
my professor uses uvwxy instead of uvxyz this confused me so much
what if i take u=aa v=aa x=bbbb y=cc and z=cc in that case no matter what is i it'll always be same
What happens when we take i=1
Please reply sir🙏🙏
Failed
What if we take i=1.....then it becomes a context free...
Do not follow this method. Method of contradiction only works if the statement claims to be true for "all" values of p, not when it says "there exists" a value of p. In this case, you have to show that no value of p exists that satisfies these conditions by assuming a general p and proceeding to disprove the language.
Chodas na bara
I don't think this is correct. You need to show that all the possible decompositions of S, THAT SATISFY the other 2 conditions, can be pumped out of the language.
check abc
Hello sir please do a example upon L={0^p| p is prime} is not a CFL
Yes sir
What if all the powers are different ?
Then it's a regular language
Straight incorrect solution, you cannot specify p value. you have proved the string with that p value does not satisfy pumping lemma, instead you should take a generic string say a^p b^p and prove that for any split and i>=0 the string will not belong to L.
It's absolutely wrong. You have to consider all the cases not an example from one case.
Awesome video sir
doesn't |vxy
Do you have to do both cases?
Thankyou Sir:)
please active auto subtitle
Sir plz tell me how we can divide the abc in uvxyz
We can select any range of symbols for any of the UVXYZ ?
do we have to make more then 1 case ???
NIET Student attendance 🤫🤫🤫 what the use of 85% attendance in college
You can't just take a random P and base your proof on that, you need to consider ALL possible values of P. Please remove this video.
sir why i is taken 2 here???? Can we take value of i as any number????
yes
UTU Students.. Give attendance !!
gaaaaaaaaaaaaalaaaaaaaaatttttttttttttttttt
Is it necessary to do more than 1 case doing a pumping lemma contradiction proof for context free languages? All the examples I see online prove with at least 2 or more cases, but no one actually explains why. Is it sufficient to disprove with 1 case?
if you prove by one case it´s enough
but if you don´t find any contradiction, you have to try all cases
I think thats wrong ... The reason multiple cases are used is because you have to show, that NOT A SINGLE uvxyz decomposition exists, such that all three conditions are satisfied.
To give a counter example to Nesos Answer: L = {a^nb^n} is a context-free language. However if you choose v such that it contains as and bs, condition 1 will not be satisfied. However, that doesnt mean that L is not context-free.
Werbung Schrott it took me 16 hours to get this conjecture. And you have confirmed my guess. Thank you. I hate teacher/professor that doesn't teach properly!!
No.
The Pumping Lemma says that there EXISTS a decomposition with the attributes. So you have to show that every single possible case is not in the language after being pumped.
Wrongggggg
Sir, can we take any value for p=1,2,... Or not
We can.
Veryy niiccceeeeeeeeeeeee
4 ela tisukunav ra munda
everyone watch easy theory this guy is a crook guy. only takes first example of sipser book. please.
Please consider removing video. It is wrong.
Please upload turing machine vedio
The English is annoying. Some sort of pidgin-English!
Thankyou sir