Pumping Lemma (For Context Free Languages) - Examples (Part 1)

  Рет қаралды 583,702

Neso Academy

Neso Academy

Күн бұрын

TOC: Pumping Lemma (For Context Free Languages) - Examples (Part 1)
This lecture shows an example of how to prove that a given language is Not Context Free using Pumping Lemma For Context Free Languages
Contribute: www.nesoacademy...
Website ► www.nesoacademy...
Facebook ► goo.gl/Nt0PmB
Twitter ► / nesoacademy
Pinterest ► / nesoacademy
Music:
Axol x Alex Skrindo - You [NCS Release]
• Axol x Alex Skrindo - ...

Пікірлер: 132
@TheTerminakill
@TheTerminakill 7 жыл бұрын
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|
@AmirBecha94
@AmirBecha94 6 жыл бұрын
same thing here! it's confusing me
@mayiwang
@mayiwang 6 жыл бұрын
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
@harshatunuguntla6462
@harshatunuguntla6462 6 жыл бұрын
suffering from the same doubt
@spamspam5741
@spamspam5741 5 жыл бұрын
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
@chanchalmaji1456
@chanchalmaji1456 5 жыл бұрын
Yes the proof is wrong, see the next example he has changed the approach
@athulsanjeevan5293
@athulsanjeevan5293 5 жыл бұрын
kudos to students from ktu.. you are not the only "one"....
@Unknown77771.
@Unknown77771. 9 ай бұрын
Ktu 2024
@daddymoist7345
@daddymoist7345 7 жыл бұрын
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
@supremepancakes4388
@supremepancakes4388 6 жыл бұрын
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.
@MrCmon113
@MrCmon113 6 жыл бұрын
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.
@willingtushar
@willingtushar 7 жыл бұрын
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
@ProfessionalTycoons
@ProfessionalTycoons 6 жыл бұрын
2:39 I think he says that we are only going to concentrate on condition 1
@ilyaskarimov175
@ilyaskarimov175 6 жыл бұрын
That is the reason why i went back to comments...
@danteeep
@danteeep 3 жыл бұрын
+1 should be should be |vxy|
@666drinking666
@666drinking666 7 жыл бұрын
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
@KayDee_88 5 жыл бұрын
but doesn't that mean the 3rd condition isn't met and hence A ain't CFL as we previously assumed??
@MultiIno123
@MultiIno123 5 жыл бұрын
@@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.
@ansonbarreto3661
@ansonbarreto3661 4 ай бұрын
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
@girishtripathy3354
@girishtripathy3354 4 жыл бұрын
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".
@brainify6172
@brainify6172 4 жыл бұрын
he's explaining the concept only by taking p = some value, but while you are proving you have to generalise.
@sumedhakamble9164
@sumedhakamble9164 5 жыл бұрын
L={a^i b^j c^k l I
@ProfessionalTycoons
@ProfessionalTycoons 6 жыл бұрын
the | vxy | length have to be smaller or equal to p
@marcoantoniorosadasilva3671
@marcoantoniorosadasilva3671 10 ай бұрын
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!!!!!
@chelseamensah1732
@chelseamensah1732 6 ай бұрын
holy cow I dont know how you made me understand that in just 12 minutes. I was struggling with this too much
@LuvnPayne45
@LuvnPayne45 6 жыл бұрын
Your case 1 is invalid. |vxy| is greater than your pumping length 4.
@isam3l3
@isam3l3 3 жыл бұрын
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
@aayushchaulagain5324
@aayushchaulagain5324 Жыл бұрын
I am confused while testing you having taken |vxy|>=p which contradicts your previous lecture's steps.
@junaidkhalidi7099
@junaidkhalidi7099 3 жыл бұрын
your both cases are wrong , |vxy| should be less than or equal to 'p' .
@pramodkoushiktr1895
@pramodkoushiktr1895 3 жыл бұрын
yes u r ryt!
@iabukai
@iabukai 6 жыл бұрын
index: it is also called Bar-Hillel Lemma
@eck1997rock
@eck1997rock 6 жыл бұрын
How do you just choose P? Doesn't it say ∃P ?
@ridwannana-yawamoako2939
@ridwannana-yawamoako2939 7 жыл бұрын
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.
@niteshswarnakar
@niteshswarnakar 3 жыл бұрын
that's what i have been searching for why this specifically ?
@AllVideos96104
@AllVideos96104 3 жыл бұрын
if we put i= 1 in case 1 then what should we get ?
@MrCmon113
@MrCmon113 6 жыл бұрын
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.
@bharathhegde4665
@bharathhegde4665 Жыл бұрын
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
@HishaMized
@HishaMized Жыл бұрын
Incorrect division of string in Case 1. The string was supposed to be divided into uvxyz in such a way that | vxy |
@GoodBoy-my8mv
@GoodBoy-my8mv Жыл бұрын
So according to this a^n b^n is also not a CFL
@sunilmanikandan4387
@sunilmanikandan4387 3 жыл бұрын
What is the difference between pumping lema for non regular and pumping lema for context free?
@weeeju
@weeeju 5 жыл бұрын
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.
@Amitsa299
@Amitsa299 7 жыл бұрын
your pace is awesome.
@MuhammadUsamaQamar
@MuhammadUsamaQamar 5 жыл бұрын
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
@saiprakash2514
@saiprakash2514 3 жыл бұрын
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??
@divyaagarwal3091
@divyaagarwal3091 2 жыл бұрын
Thankyou sir
@aniketsaxena1892
@aniketsaxena1892 4 жыл бұрын
What happens when we take i=1 Please reply sir🙏🙏
@shijinrejiabraham6806
@shijinrejiabraham6806 3 жыл бұрын
Failed
@devmahad
@devmahad 11 ай бұрын
Done - thanks
@USBEN.
@USBEN. 5 жыл бұрын
We can select any range of symbols for any of the UVXYZ ?
@shaswatpatra4716
@shaswatpatra4716 Жыл бұрын
sir why i is taken 2 here???? Can we take value of i as any number????
@topcubasov8942
@topcubasov8942 4 ай бұрын
yes
@y01cu_yt
@y01cu_yt 2 жыл бұрын
Thanks!
@brensenvillegas7177
@brensenvillegas7177 Жыл бұрын
doesn't |vxy
@matthewlev1342
@matthewlev1342 4 жыл бұрын
Do you have to do both cases?
@danialsaeed1083
@danialsaeed1083 4 жыл бұрын
do we have to make more then 1 case ???
@DrAmitkumarPathak
@DrAmitkumarPathak Жыл бұрын
If S>P then how you have taken P=4 ??
@worshiperdot3677
@worshiperdot3677 3 жыл бұрын
brilliantly explained
@rukaiyayaqoob6545
@rukaiyayaqoob6545 2 жыл бұрын
Sir plz tell me how we can divide the abc in uvxyz
@ancient1844
@ancient1844 21 күн бұрын
Incorrect. There is a rule that the length of vxy must be less than or equal to p.
@nonelelacele9300
@nonelelacele9300 2 жыл бұрын
well explained
@pirateboygaming2726
@pirateboygaming2726 6 ай бұрын
The same question is on Wikipedia. Yiu can check it out to solve it the correct way.
@stephanielfagan
@stephanielfagan 7 жыл бұрын
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?
@jh007x
@jh007x 7 жыл бұрын
if you prove by one case it´s enough
@jh007x
@jh007x 7 жыл бұрын
but if you don´t find any contradiction, you have to try all cases
@werbungschrott4050
@werbungschrott4050 6 жыл бұрын
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.
@siegfredch.960
@siegfredch.960 6 жыл бұрын
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!!
@MrCmon113
@MrCmon113 6 жыл бұрын
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.
@nandishkr7864
@nandishkr7864 3 жыл бұрын
What if we take i=1.....then it becomes a context free...
@aishu6653
@aishu6653 Жыл бұрын
Any one case is enough for exam right?? 👀
@dhakshinar
@dhakshinar 7 жыл бұрын
Pls upload other videos push down Automata, Turing machine..
@ashis9324
@ashis9324 5 жыл бұрын
Hello sir please do a example upon L={0^p| p is prime} is not a CFL
@rukaiyayaqoob6545
@rukaiyayaqoob6545 2 жыл бұрын
Yes sir
@jskzo
@jskzo Жыл бұрын
It is not correct to take a particular value of the pumping length. One needs to prove for all possible pumping length.
@ayushidhingra9756
@ayushidhingra9756 6 жыл бұрын
What if all the powers are different ?
@patvax137
@patvax137 6 жыл бұрын
Then it's a regular language
@aneeshagarwal4746
@aneeshagarwal4746 11 ай бұрын
You the goat
@neEs6624
@neEs6624 Жыл бұрын
Awesome
@manikanta-oh3qy
@manikanta-oh3qy 7 жыл бұрын
Sir plz upload electromagnetics for ece lectures...
@julakantigopi2783
@julakantigopi2783 5 жыл бұрын
Sir, can we take any value for p=1,2,... Or not
@asthaneupane2514
@asthaneupane2514 5 жыл бұрын
We can.
@francescapugliese3096
@francescapugliese3096 3 жыл бұрын
PERFECT!
@deepneon
@deepneon 4 жыл бұрын
you have totally messed it up, sir!! I came here for simplification , but huhhhhhhhhhhhhh :XD
@MinhLe-xk5rm
@MinhLe-xk5rm 5 жыл бұрын
Awesome video sir
@oguzhan4927
@oguzhan4927 6 жыл бұрын
Sen nasil bi kralsin ya ..
@cengci_faruk
@cengci_faruk 2 жыл бұрын
dogrusun
@poojamahanand8021
@poojamahanand8021 7 жыл бұрын
Thankyou Sir:)
@martian0x80
@martian0x80 4 ай бұрын
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.
@innociduousnepheliad8140
@innociduousnepheliad8140 11 ай бұрын
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.
@arkodeepbanik1623
@arkodeepbanik1623 5 ай бұрын
Chodas na bara
@ayushsharma397
@ayushsharma397 5 ай бұрын
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.
@testphp667
@testphp667 4 жыл бұрын
check abc
@arpitsharma-c4n
@arpitsharma-c4n 5 ай бұрын
NIET Student attendance 🤫🤫🤫 what the use of 85% attendance in college
@4.5مليون
@4.5مليون 2 жыл бұрын
please active auto subtitle
@vatsalgp
@vatsalgp 4 жыл бұрын
It's absolutely wrong. You have to consider all the cases not an example from one case.
@auwee7251
@auwee7251 4 жыл бұрын
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.
@rumanzahid6671
@rumanzahid6671 5 жыл бұрын
Veryy niiccceeeeeeeeeeeee
@malvikapathak4971
@malvikapathak4971 7 жыл бұрын
Please upload turing machine vedio
@sksp9028
@sksp9028 2 жыл бұрын
gaaaaaaaaaaaaalaaaaaaaaatttttttttttttttttt
@rahulsyt_
@rahulsyt_ 2 жыл бұрын
UTU Students.. Give attendance !!
@vaibhzDixit
@vaibhzDixit Жыл бұрын
Wrongggggg
@omersohail1067
@omersohail1067 2 жыл бұрын
everyone watch easy theory this guy is a crook guy. only takes first example of sipser book. please.
@neeraj8867
@neeraj8867 3 жыл бұрын
4 ela tisukunav ra munda
@onemanshow4116
@onemanshow4116 4 жыл бұрын
Please consider removing video. It is wrong.
@passamaquoddy8311
@passamaquoddy8311 3 жыл бұрын
The English is annoying. Some sort of pidgin-English!
@dhanushsivajaya1356
@dhanushsivajaya1356 3 жыл бұрын
Thankyou sir
Pumping Lemma (For Context Free Languages) - Examples (Part 2)
17:44
Pumping Lemma (For Context Free Languages)
8:06
Neso Academy
Рет қаралды 669 М.
Миллионер | 1 - серия
34:31
Million Show
Рет қаралды 2,9 МЛН
My Daughter's Dumplings Are Filled With Coins #funny #cute #comedy
00:18
Funny daughter's daily life
Рет қаралды 30 МЛН
Mom had to stand up for the whole family!❤️😍😁
00:39
Pumping Lemma (For Regular Languages) | Example 1
14:16
Neso Academy
Рет қаралды 1,2 МЛН
Theory of Computation: Pumping Lemma for Regular Languages
12:33
The Wordpress drama keeps getting worse
12:47
Theo - t3․gg
Рет қаралды 97 М.
Context-Free Grammars (CFGs): 5 Easy Examples
19:03
Easy Theory
Рет қаралды 48 М.
Pumping Lemma for Context-Free Languages, Statement and FULL PROOF
30:03
Equivalence of CFG and PDA (Part 1)
22:49
Neso Academy
Рет қаралды 713 М.
If Your Tech Job is Comfortable, You're in Danger
20:57
Thriving Technologist
Рет қаралды 21 М.
Pumping Lemma (For Regular Languages)
8:08
Neso Academy
Рет қаралды 1,3 МЛН
What is the Pumping Lemma
5:11
lydia
Рет қаралды 122 М.
Миллионер | 1 - серия
34:31
Million Show
Рет қаралды 2,9 МЛН