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

[@athulsanjeevan5293]

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

[@UNKNOWN-i2v]

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.

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

[@ProfessionalTycoons]

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

[@LuvnPayne45]

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

[@sumedhakamble9164]

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

[@iabukai]

index: it is also called Bar-Hillel Lemma

[@junaidkhalidi7099]

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

[@pramodkoushiktr1895]

yes u r ryt!

[@Amitsa299]

your pace is awesome.

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

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

[@eck1997rock]

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

[@aayushchaulagain5324]

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

[@HishaMized]

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

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

[@AllVideos96104]

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

[@aishu6653]

Any one case is enough for exam right?? 👀

[@Rajan_Jha-z7m]

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

[@sunilmanikandan4387]

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

[@nonelelacele9300]

well explained

[@DrAmitkumarPathak]

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

[@y01cu_yt]

Thanks!

[@devmahad]

Done - thanks

[@dhanushsivajaya1356]

Thankyou sir

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

[@ancient1844]

Incorrect. There is a rule that the length of vxy must be less than or equal to p.

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

[@aniketsaxena1892]

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

[@shijinrejiabraham6806]

Failed

[@worshiperdot3677]

brilliantly explained

[@pirateboygaming2726]

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

[@oguldibi]

Sen nasil bi kralsin ya ..

[@cengci_faruk]

dogrusun

[@nandishkr7864]

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

[@matthewlev1342]

Do you have to do both cases?

[@brensenvillegas7177]

doesn't |vxy

[@USBEN.]

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

[@dhakshinar]

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

[@danialsaeed1083]

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

[@manikanta-oh3qy]

Sir plz upload electromagnetics for ece lectures...

[@MinhLe-xk5rm]

Awesome video sir

[@jskzo]

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

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

[@ayushidhingra9756]

What if all the powers are different ?

[@patvax137]

Then it's a regular language

[@rukaiyayaqoob6545]

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

[@shaswatpatra4716]

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

[@topcubasov8942]

yes

[@deepneon]

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

[@aneeshagarwal4746]

You the goat

[@francescapugliese3096]

PERFECT!

[@ashis9324]

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

[@rukaiyayaqoob6545]

Yes sir

[@neEs6624]

Awesome

[@jackschneider863]

my professor uses uvwxy instead of uvxyz this confused me so much

[@poojamahanand8021]

Thankyou Sir:)

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

[@anandhasantosha4424]

[@julakantigopi2783]

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

[@asthaneupane2514]

We can.

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

[@vatsalgp]

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

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

[@4.5مليون]

please active auto subtitle

[@arpitsharma-c4n]

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

[@testphp667]

check abc

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

[@rahulsyt_]

UTU Students.. Give attendance !!

[@rumanzahid6671]

Veryy niiccceeeeeeeeeeeee

[@sksp9028]

gaaaaaaaaaaaaalaaaaaaaaatttttttttttttttttt

[@omersohail1067]

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

[@malvikapathak4971]

Please upload turing machine vedio

[@onemanshow4116]

Please consider removing video. It is wrong.

[@vaibhzDixit]

Wrongggggg

[@neeraj8867]

4 ela tisukunav ra munda

[@passamaquoddy8311]

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

[@divyaagarwal3091]

Thankyou sir