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

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 - ...

[@athulsanjeevan5293]

kudos to students from ktu.. you are not the only "one"....

[@Unknown77771.]

Ktu 2024

[@daddymoist7345]

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]

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]

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.

[@TheTerminakill]

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]

same thing here! it's confusing me

[@mayiwang]

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]

suffering from the same doubt

[@spamspam5741]

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]

Yes the proof is wrong, see the next example he has changed the approach

[@willingtushar]

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]

2:39 I think he says that we are only going to concentrate on condition 1

[@ilyaskarimov175]

That is the reason why i went back to comments...

[@danteeep]

+1 should be should be |vxy|

[@666drinking666]

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]

but doesn't that mean the 3rd condition isn't met and hence A ain't CFL as we previously assumed??

[@MultiIno123]

@@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]

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

[@chelseamensah1732]

holy cow I dont know how you made me understand that in just 12 minutes. I was struggling with this too much

[@marcoantoniorosadasilva3671]

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!!!!!

[@girishtripathy3354]

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]

he's explaining the concept only by taking p = some value, but while you are proving you have to generalise.

[@ProfessionalTycoons]

the | vxy | length have to be smaller or equal to p

[@isam3l3]

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

[@sumedhakamble9164]

L={a^i b^j c^k l I

[@iabukai]

index: it is also called Bar-Hillel Lemma

[@LuvnPayne45]

Your case 1 is invalid. |vxy| is greater than your pumping length 4.

[@Amitsa299]

your pace is awesome.

[@junaidkhalidi7099]

your both cases are wrong , |vxy| should be less than or equal to 'p' .

[@pramodkoushiktr1895]

yes u r ryt!

[@weeeju]

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.

[@devmahad]

Done - thanks

[@MrCmon113]

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.

[@y01cu_yt]

Thanks!

[@eck1997rock]

How do you just choose P? Doesn't it say ∃P ?

[@divyaagarwal3091]

Thankyou sir

[@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

[@ridwannana-yawamoako2939]

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]

that's what i have been searching for why this specifically ?

[@francescapugliese3096]

PERFECT!

[@nonelelacele9300]

well explained

[@GoodBoy-my8mv]

So according to this a^n b^n is also not a CFL

[@worshiperdot3677]

brilliantly explained

[@AllVideos96104]

if we put i= 1 in case 1 then what should we get ?

[@HishaMized]

Incorrect division of string in Case 1. The string was supposed to be divided into uvxyz in such a way that | vxy |

[@aayushchaulagain5324]

I am confused while testing you having taken |vxy|>=p which contradicts your previous lecture's steps.

[@aishu6653]

Any one case is enough for exam right?? 👀

[@pirateboygaming2726]

The same question is on Wikipedia. Yiu can check it out to solve it the correct way.

[@dhakshinar]

Pls upload other videos push down Automata, Turing machine..

[@aneeshagarwal4746]

You the goat

[@aniketsaxena1892]

What happens when we take i=1 Please reply sir🙏🙏

[@shijinrejiabraham6806]

Failed

[@manikanta-oh3qy]

Sir plz upload electromagnetics for ece lectures...

[@neEs6624]

Awesome

[@oguzhan4927]

Sen nasil bi kralsin ya ..

[@cengci_faruk]

dogrusun

[@saiprakash2514]

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??

[@ashis9324]

Hello sir please do a example upon L={0^p| p is prime} is not a CFL

[@rukaiyayaqoob6545]

Yes sir

[@deepneon]

you have totally messed it up, sir!! I came here for simplification , but huhhhhhhhhhhhhh :XD

[@MuhammadUsamaQamar]

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

[@USBEN.]

We can select any range of symbols for any of the UVXYZ ?

[@sunilmanikandan4387]

What is the difference between pumping lema for non regular and pumping lema for context free?

[@DrAmitkumarPathak]

If S>P then how you have taken P=4 ??

[@arpitsharma-c4n]

NIET Student attendance 🤫🤫🤫 what the use of 85% attendance in college

[@brensenvillegas7177]

doesn't |vxy

[@matthewlev1342]

Do you have to do both cases?

[@rukaiyayaqoob6545]

Sir plz tell me how we can divide the abc in uvxyz

[@nandishkr7864]

What if we take i=1.....then it becomes a context free...

[@danialsaeed1083]

do we have to make more then 1 case ???

[@ayushidhingra9756]

What if all the powers are different ?

[@patvax532]

Then it's a regular language

[@jskzo]

It is not correct to take a particular value of the pumping length. One needs to prove for all possible pumping length.

[@shaswatpatra4716]

sir why i is taken 2 here???? Can we take value of i as any number????

[@topcubasov8942]

yes

[@martian0x80]

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.

[@testphp667]

check abc

[@4.5مليون]

please active auto subtitle

[@innociduousnepheliad8140]

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]

Chodas na bara

[@vatsalgp]

It's absolutely wrong. You have to consider all the cases not an example from one case.

[@stephanielfagan]

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]

if you prove by one case it´s enough

[@jh007x]

but if you don´t find any contradiction, you have to try all cases

[@werbungschrott4050]

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]

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]

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.

[@julakantigopi2783]

Sir, can we take any value for p=1,2,... Or not

[@asthaneupane2514]

We can.

[@ayushsharma397]

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.

[@poojamahanand8021]

Thankyou Sir:)

[@auwee7251]

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.

[@MinhLe-xk5rm]

Awesome video sir

[@sksp9028]

gaaaaaaaaaaaaalaaaaaaaaatttttttttttttttttt

[@rumanzahid6671]

Veryy niiccceeeeeeeeeeeee

[@neeraj8867]

4 ela tisukunav ra munda

[@malvikapathak4971]

Please upload turing machine vedio

[@omersohail1067]

everyone watch easy theory this guy is a crook guy. only takes first example of sipser book. please.

[@onemanshow4116]

Please consider removing video. It is wrong.

[@vaibhzDixit]

Wrongggggg

[@rahulsyt_]

UTU Students.. Give attendance !!

[@passamaquoddy8311]

The English is annoying. Some sort of pidgin-English!

[@dhanushsivajaya1356]

Thankyou sir