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

Music:
Axol x Alex Skrindo - You [NCS Release]

[athulsanjeevan]

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

[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| <= P

[daddymoist]

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

[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<=p.

sir, please take a look at what I am saying and also you says at 7:44 that "since condition 1 is not true than, there is no point in checking the other ones" but my dear friend when we split the string into uvxyz, the all three must be satisfied (coz these aren't the steps but these are the conditions) like |vy| >0 means that neither of two can be of zero length(means we can have a epsilon)etc.

hope you read this...

[marcoantoniorosadasilva]

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

[drinking]

both examples are wrong. The pumping lemma states that |vxy| <= p. your p is 4 but in both examples you divided your uvxyz so 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

[isaml]

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

[girishtripathy]

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

[ProfessionalTycoons]

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

[LuvnPayne]

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

[sumedhakamble]

L={a^i b^j c^k l I<j<k} please suggest me what is length p=?

[chelseamensah]

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

[eckrock]

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

[AllVideos]

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

[iabukai]

index: it is also called Bar-Hillel Lemma

[USBEN.]

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

[ridwannana-yawamoako]

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.

[sunilmanikandan]

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

[rukaiyayaqoob]

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

[dhakshinar]

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