Thank You Neso Academy! Today was my End Semester exam of TCS, and your playlist helped me a lot in my preparation. I literally start studying 2 days before and lost hope completely but your 114 videos came to the rescue. THANK YOU SO MUCH :))
for all those asking why we need it to prove all the cases for pumping lemma, you have to prove that it does not satisfy each and every case possible ie:- you can disprove a specific case by taking an example but you cannot prove it is not cnf just by taking one case you have to prove for all cases Explanation:- while deriving the pushdown automata for cnf we assume it to be the form uvxyz but do not specify any boundaries or restrictions on the values uvxyz will take so to disprove that the language is not in CFL we need to consider all the cases
how do you know for the splitting(uvxyz) how many numbers must each have ? EG. case 2a u has 3=> 0's vxy has 2=> 0's and 3=> 1's and z has 7 => 1's and 5=> 0's . how do we split them?
Since {0,1}* can have any combination of 0s and 1s, then we could have w=00011 (for example). So ww=0001100011, which is in L. Then let u=000, v=1, x=10001, y=1, z=1, and P=1000 (because I don't see why we need to have 0^P 1^P 0^P 1^P; there was no requirement of this in the Pumping Lemma). So, |vxy|=70, and uv^2xy^2z=000111000111, which is in L, and for i=3, 00011110001111 is also in L because we can have 0^j 1^k 0^j 1^k (because j and k don't need to be the same to be in L, we just need the powers j and k to repeat so that we get ww). This would suggest that L is a CFL, unless there's some piece of information I'm missing. If anyone disagrees, please let me know.
To show that a language L fails to be regular, we must show that for any choice of p(p>=0) we can find an s∈L such that every possible partition of s will violate one or more of the three conditions.
the langauge is L = { ww | w belongs {0,1}*} if you look well you see ww in L which means make any combination of {0,1}* but first half w should be the same as second half w which explains ww in language
Nicely done video! Just be careful to assume a double implication on the application of this lemma. In other words, showing contradiction demonstrates that the language is not context-free. Complying with the pumping lemma DOES NOT DEMONSTRATES THE LANGUAGE IS CONTEXT-FREE. (See Chomsky Hierarchy: en.wikipedia.org/wiki/Chomsky_hierarchy ) Other detail: What happen if x is the empty string? The lemma does not forbid that at all. In this case, the are lose of generality. Either way, I truly appreciate the explanation. It was very didactic. Just that. Thank you for your work.
I believe this is just something "discovered." These aren't cases set in stone. If you can come up with your own technique/case as long as it works. You do not have to go by the exact ones he does, I believe.
For one string our condition got wrong then what is the need to check for more strings Since single string which doesn't satisfy conditions is enough to prove that language is not cfl
can you plzz explain how are we dividing the strings previous case you divided in different cases and conditions now another how do we know when we have to use which condition
I've got a question. When the professor in the video talks about how vxy should be greater than p, does he mean that I have to to multiply the amount of symbols each of v, x, and y span accross? or does he mean that I should just add them?
It's easy Use the most minimal condition applicable in the language What would that be ? It would be i=j=k right then you can say c is a CFL and form a pumping lemma for it ,now that could be p=4 and then let , i=j=k=p=4 and ,by using next usual steps you can prove that its not a cfl
For anyone who may come across this comment in the near future & shares the query, here's what I believe: We took the cases for vxy first so that we may satisfy condition 3 to begin with. And then whatever is left, assign all before it as "u" & all after it as "z". The part that we've taken as "vxy", we can randomly assign any no. of symbols to v, x or y randomly. Only thing to keep in mind is that combined length of |vxy| shall be less than or equal to Pumping Length P. So note that if condition 3 is satisfied, then condition 2 holds true as well. So we just need to check for condition 1, i.e., whether the string formed belongs to the language or not. And if 1 fails, then it's a contradiction to our assumption. And we can say L is not CFL.
Acc to me Yes as there's no such boundary for the pattern of 0s and 1s the only information that we've is that it must a combination of 0s and 1s, no pattern as 0^n1^n is required but I think this is taken so that we can get an answer with min no of steps
Sir, why we need to check all the cases?? I believe we can go through any of the case?? Proving for one time that the generated string doesn't belongs to L is enough rite??
for all those asking why we need it to prove all the cases for pumping lemma, you have to prove that it does not satisfy each and every case possible ie:- you can disprove a specific case by taking an example but you cannot prove it is not cnf just by taking one case you have to prove for all cases Explanation:- while deriving the pushdown automata for cnf we assume it to be the form uvxyz but do not specify any boundaries or restrictions on the values uvxyz will take so to disprove that the language is not in CFL we need to consider all the cases
Hallo! Congratulations for your helpful lessons! Can you explain to me the pattern you use to select the letters are going to be u, the letters are going to be v etc? Do you choose them by chance? Thanks!
After watching videos on Pumping Lemma for Regular Languages and CFL, I think in this way - We can make many cases for the five parts (uvxyz) and show that pumping conditions are not satisfied in any of the case at the same time. I think Instructor mentioned this in one of the videos of Pumping Lemma for Regular Languages. Let me know if there is something else.
When you do these proofs, you aren't allowed to assign uvxyz to a certain section. We have no idea how the symbols are arranged in the given string. You also cannot make a concrete example to prove something. You have to keep it in terms of p (in your case), otherwise its just proving one example string.
Actually as far as I know, to prove something we have to prove it in general terms but if we have to disprove something even one case or example is enough because then it is proved that it is not valid for all cases. And we are doing the same here.
You are absolutely correct but I'm afraid where these conditions came from ...............i couldn't find these condition in my textbook neither in google.
0^p1^p0^p1^p denotes all symble exist in the string shoud have same length.....but i L=WW means there must be following two string will be have same...inorder to acheive S=0^n1^m0^n1^m...............am i right?
This is great! Just one question, what do you do if you have an exercise in which the powers are all different. Example (from an exercise) L1 = {0^m 1^k 2^n | n = km} . how do I apply the pumping length to this? My first guess was to just simply add p to each power i.e (0^PM 1^PK 2 ^PN) , when I select P as , say, 3. I would ALSO have to select n, k, m so that the string satisfies the property of the language (n = km). This leads to my follow-up question: When I have my string, s, and then want to divide it, should I divide it so that (2) and (3) are satisfied before moving on to testing 1? What happens if (2) is not satisfied?
What are you writing, your question is not clear , either write properly or put a question link Any way if you are asking about how to approach the language with condition n=km Then just take m=2,k=3,n=6 and then take p=10 since |L1| will be 11 i.e. greater than P so now you can proceed as usual
This proof only checked for p = 5. But the lemma assume that some for some p, we can satisfy the three condition. Don't we have to prove the above for all value of p? In addition, how do you prove that the above cases cover all possible ways to divide S into uvxyz ?
In this example if we assume that one case is true then can we make an assumption that it can be context free language or all conditions should be satisfied
W belongs to any combination of 0s and 1s and as we're given the L = WW, which means whatever the combination of 0s and 1s we're taking for first W, the second W must also be the same. that's what WW means that whatever string is the first one the second string should be the same as well.
you need to prove for all the cases and also for all the values of P(pumping length) so, you should not assume p to have any value instead use more generalized method to solve the problem
Hello plz help me, i want to know that, even if a single case fails the pumping test then we can say a language is not context-free or we need to check all the cases to test?
why did we devide u vxy and z in that manner? Could also devide it so that u, vxy and z are equally long? I always struggle with deviding it cause idk how
ok I guess i asked the wrong thing. obviously the boundary comes from the numbers of symbols in a word. And I guess if we check for case 1 we need to take any boundary and make vxy max. as long as the boundary itself. But could I also say Ill make my vxy 11111 instead of 111 as in the example ? The result would be the same obviously but is that still possible? oh damn and again I found the answer myself xD we can choose the length as long as its
Sorry. If any one case satisfies all 3 conditions then we cannot say whether it is context free or not. Only if no case satisfies all 3 conditions can we say that it's *not* context free. The video is actually wrong about this. :S
Thank You Neso Academy! Today was my End Semester exam of TCS, and your playlist helped me a lot in my preparation. I literally start studying 2 days before and lost hope completely but your 114 videos came to the rescue. THANK YOU SO MUCH :))
for all those asking why we need it to prove all the cases
for pumping lemma, you have to prove that it does not satisfy each and every case possible
ie:- you can disprove a specific case by taking an example
but you cannot prove it is not cnf just by taking one case you have to prove for all cases
Explanation:-
while deriving the pushdown automata for cnf we assume it to be the form uvxyz but do not specify any boundaries or restrictions on the values uvxyz will take so to disprove that the language is not in CFL we need to consider all the cases
Thanks
But if it is failed for one case that's enough to show that it is not CFL,is it?
how do you know for the splitting(uvxyz) how many numbers must each have ? EG. case 2a u has 3=> 0's vxy has 2=> 0's and 3=> 1's and z has 7 => 1's and 5=> 0's . how do we split them?
lecture with huge efforts
Since {0,1}* can have any combination of 0s and 1s, then we could have w=00011 (for example). So ww=0001100011, which is in L. Then let u=000, v=1, x=10001, y=1, z=1, and P=1000 (because I don't see why we need to have 0^P 1^P 0^P 1^P; there was no requirement of this in the Pumping Lemma). So, |vxy|=70, and uv^2xy^2z=000111000111, which is in L, and for i=3, 00011110001111 is also in L because we can have 0^j 1^k 0^j 1^k (because j and k don't need to be the same to be in L, we just need the powers j and k to repeat so that we get ww). This would suggest that L is a CFL, unless there's some piece of information I'm missing. If anyone disagrees, please let me know.
I was thinking about this too..
To show that a language L fails to be regular, we must show that for any choice of p(p>=0) we can find an s∈L such that every possible partition of s will violate one or more of the three conditions.
You took p=4 and your |vxy|=7 so |vxy|>P which is not the condition so the given language is not context free
the langauge is L = { ww | w belongs {0,1}*} if you look well you see ww in L which means make any combination of {0,1}* but first half w should be the same as second half w which explains ww in language
vxy should have a length less than or equal to p. But in the previous video of pumping lemma , this rule was not followed ?
I believe in the previous video, he said lets only focus on condition 1
Because if 1 condition is not satisfying then if 2 0r 3 will satisfy ,it's of no use .so he just focused on 1 one if you want you can check.
Same Doubt here
Sir, In the above example by solving case-1, what we'll consider values of VXY, if cardinality of any boundary is less than 3
8:22 what if the final string DID belong to L? Then should we just go through a bunch of (i)s to find an (i) where u.v^i.x.y^i.z belongs to L?
Nicely done video!
Just be careful to assume a double implication on the application of this lemma. In other words, showing contradiction demonstrates that the language is not context-free. Complying with the pumping lemma DOES NOT DEMONSTRATES THE LANGUAGE IS CONTEXT-FREE.
(See Chomsky Hierarchy: en.wikipedia.org/wiki/Chomsky_hierarchy )
Other detail: What happen if x is the empty string? The lemma does not forbid that at all. In this case, the are lose of generality.
Either way, I truly appreciate the explanation. It was very didactic.
Just that. Thank you for your work.
I somehow feel I prove everything NOT a language :0
@@gyanig8501 well if you prove its not a language, you're fine.
thanks a great for all the videos sir,,,,,,,,
please make all the syllabus videos as soon as possible
sir where are these cases coming from?
practice
I believe this is just something "discovered." These aren't cases set in stone. If you can come up with your own technique/case as long as it works. You do not have to go by the exact ones he does, I believe.
@@nathanieloakleaves5789 sir we can use some constant cases or not
@@nathanieloakleaves5789 so, how do you decide which way to take the cases?
@@SuryaBoddu Its your choice...what cases you will take...you just have to show that it is not cfl
For one string our condition got wrong then what is the need to check for more strings
Since single string which doesn't satisfy conditions is enough to prove that language is not cfl
so i can come up with cases like v and y lies in 1's part somethings like that too
do we have to prove all cases ? or proving only one case is enought?
I think only one case is enough to prove the language is not context free
It's really very very helpful sir 👍
Thank you so much sir 🙏the way you Teach is awesome
we share the similar usernames lol
can you plzz explain how are we dividing the strings previous case you divided in different cases and conditions now another how do we know when we have to use which condition
divide it in any way you only need to make sure that:-
|vy|>0
|vxy|
I've got a question. When the professor in the video talks about how vxy should be greater than p, does he mean that I have to to multiply the amount of symbols each of v, x, and y span accross? or does he mean that I should just add them?
You do not mention how you decide the cases? How to know what will be the cases?
@Pro Dev what?
@Dev D Whaaaat
sir will you please explain this example
C = {a^ib^jc^k|0 ≤ i ≤ j ≤ k}. use the pumping lemma to show that C is not a CFL
thanks..
It's easy
Use the most minimal condition applicable in the language
What would that be ?
It would be i=j=k right then you can say c is a CFL and form a pumping lemma for it ,now that could be p=4 and then let , i=j=k=p=4 and ,by using next usual steps you can prove that its not a cfl
why are we considering V,X,Y but not V & Y like previous example, someone pls explain.
For anyone who may come across this comment in the near future & shares the query, here's what I believe:
We took the cases for vxy first so that we may satisfy condition 3 to begin with. And then whatever is left, assign all before it as "u" & all after it as "z".
The part that we've taken as "vxy", we can randomly assign any no. of symbols to v, x or y randomly. Only thing to keep in mind is that combined length of |vxy| shall be less than or equal to Pumping Length P.
So note that if condition 3 is satisfied, then condition 2 holds true as well. So we just need to check for condition 1, i.e., whether the string formed belongs to the language or not. And if 1 fails, then it's a contradiction to our assumption. And we can say L is not CFL.
@@RA-gv3ysHopefully, people like u exist. thanks man!
If 1st case itself failed why do we need to check other cases?
Can we consider 'w' as 0^a1^b
ww will become 0^a 1^b 0^a 1^b
Correct me if I am wrong
Acc to me Yes as there's no such boundary for the pattern of 0s and 1s the only information that we've is that it must a combination of 0s and 1s, no pattern as 0^n1^n is required but I think this is taken so that we can get an answer with min no of steps
Sir please solve a^n b^2n |n>0 is regular or not
Sir, why we need to check all the cases?? I believe we can go through any of the case?? Proving for one time that the generated string doesn't belongs to L is enough rite??
how to decide which type of cases we have to make like for every question there are different kind of cases
how will we divide s and how can we understand the cases for a problem.
sir, question doesn't say 0 has to come first, so can we take string as 1^p 0^p if we want to?
Can we solve this example,by only using condition-1????
If we,then these 4 cases is really needed to do that???
index: it is also called Bar-Hillel Lemma
Thankyou sir
how do we decide the cases
is it necessary to consider all the diff cases if the first case we pick fails?
My doubt is alos same
Anybody plz answer
for all those asking why we need it to prove all the cases
for pumping lemma, you have to prove that it does not satisfy each and every case possible
ie:- you can disprove a specific case by taking an example
but you cannot prove it is not cnf just by taking one case you have to prove for all cases
Explanation:-
while deriving the pushdown automata for cnf we assume it to be the form uvxyz but do not specify any boundaries or restrictions on the values uvxyz will take so to disprove that the language is not in CFL we need to consider all the cases
Why in the previous video we didn't take cases of straddle boundary???
that was totally wrong i guess !!!
why the cases are different when compare to previous video
Hallo! Congratulations for your helpful lessons! Can you explain to me the pattern you use to select the letters are going to be u, the letters are going to be v etc? Do you choose them by chance? Thanks!
After watching videos on Pumping Lemma for Regular Languages and CFL, I think in this way - We can make many cases for the five parts (uvxyz) and show that pumping conditions are not satisfied in any of the case at the same time. I think Instructor mentioned this in one of the videos of Pumping Lemma for Regular Languages. Let me know if there is something else.
how to know the cases in previous vid cases were different and in this case is different ??/
I think if we put i=2 then the first condition is satisfies in all the cases... It my opinion
When you do these proofs, you aren't allowed to assign uvxyz to a certain section. We have no idea how the symbols are arranged in the given string. You also cannot make a concrete example to prove something. You have to keep it in terms of p (in your case), otherwise its just proving one example string.
Actually as far as I know, to prove something we have to prove it in general terms but if we have to disprove something even one case or example is enough because then it is proved that it is not valid for all cases. And we are doing the same here.
But in this case he is not trying to disprove the original statement, he is actually trying to PROVE the opposite - prove by contradition
You are absolutely correct but I'm afraid where these conditions came from ...............i couldn't find these condition in my textbook neither in google.
Page 129, Example 2.38, in Introduction to the theory of computation by M. Sipser 3rd Ed. (check out gen,lib,rus,ec if you need a copy)
How do you decide these cases?
it is necessary to show all cases while solving in examination?????
0^p1^p0^p1^p denotes all symble exist in the string shoud have same length.....but i L=WW means there must be following two string will be have same...inorder to acheive S=0^n1^m0^n1^m...............am i right?
yup
This is great! Just one question, what do you do if you have an exercise in which the powers are all different. Example (from an exercise) L1 = {0^m 1^k 2^n | n = km} . how do I apply the pumping length to this? My first guess was to just simply add p to each power i.e (0^PM 1^PK 2 ^PN) , when I select P as , say, 3. I would ALSO have to select n, k, m so that the string satisfies the property of the language (n = km). This leads to my follow-up question: When I have my string, s, and then want to divide it, should I divide it so that (2) and (3) are satisfied before moving on to testing 1? What happens if (2) is not satisfied?
fail only
What are you writing, your question is not clear , either write properly or put a question link
Any way if you are asking about how to approach the language with condition n=km
Then just take m=2,k=3,n=6 and then take p=10 since |L1| will be 11 i.e. greater than P so now you can proceed as usual
Sir is it sufficient to prove it for just one case ??? Because if you prove that one case is failed then it is not CFL,it's already proved
are we suppose to check for each case possible?.....can't we just conclude for any one case that it is not context free .....?
bhai kal no. chahiye to saare case likhdio
This proof only checked for p = 5. But the lemma assume that some for some p, we can satisfy the three condition. Don't we have to prove the above for all value of p? In addition, how do you prove that the above cases cover all possible ways to divide S into uvxyz ?
it wont satisfy all the conditions for any P, if its not context free
@@anuragparcha4483 then why you are taking only 3 cases??
What is the need for taking cases??
@@sameeranerella1120 honestly bro idk. I did this more than a year back and never used it after.
why are we even checkingthe other cases when even first case failed?
u could be 0^p
In this example if we assume that one case is true then can we make an assumption that it can be context free language or all conditions should be satisfied
Why are we taking different cases? If it doesn't satisfy one case can't we simply conclude that it is not cfl
do we need to check for every case or we can say its not CFL if it fails even a single case?
why are we saying that first part should be equal to second part????0^5 1^5 0^7 1^7 will also be accepted by (0,1)*
W belongs to any combination of 0s and 1s and as we're given the L = WW, which means whatever the combination of 0s and 1s we're taking for first W, the second W must also be the same. that's what WW means that whatever string is the first one the second string should be the same as well.
@@lakshmansingh3162 ohhh...thanks🤝
do i have to take all cases or can i simply prove with only one case
If we prove it as contradiction for 1 case so do we need to prove it for all the cases also ??
you need to prove for all the cases
and also for all the values of P(pumping length)
so, you should not assume p to have any value instead use more generalized method to solve the problem
if A LL THE CONDITIONS ARE SATISFIED BY THIS LANGUAGE,SIR CAN WE ALLOWED TO CONCLUDE THAT AS CONTEXT FREE?
no it can't be used to prove that a language is context free
Is this needed to check all cases to check the given language is CFL
Can you try Pumping Lemma on a real CFL? Let say on a palindrome? I want that because when I try it o a real CFL, still I find that it is not CFL.
pumping lemma can only prove a language to be not cfl, it cannot prove a language is cfl
Is it okay to prove by only one case or we have to prove by both the cases..................and in the prevoius video condition vxy
please explain membership algorithm
Do we need to prove all cases? How do we create cases properly?
on what basis he is taking case 1 and case 2 bcz in previous lecture he has takes diff case but in this he has taken diff
How to find out boundery of vxy ?
I just proved a^n b^n is not context free using Pumping Lemma even though it is a context free language wtf
happens dont use it for cflonly use it to disprove
Is in this topic of any Ex Either we have to think about cases or given
Hello plz help me, i want to know that, even if a single case fails the pumping test then we can say a language is not context-free or we need to check all the cases to test?
Ha ek case se hi proof hozaeaga no need for multiple cases
How can we make cases ???
sir is it neccasary to consider all the cases if we vxy can straddle all boundaries
?
Do the solution for string S (a,b)*
if we have proved in first case only that language is not context free then why do we take those other cases
I love you yrr you saved my life. 😍😍😍
Why do you put your string powers p is it mandatory cause you juwt said s>=p
Are you sure 0^n1^n0^n1^n is not CFL ? It can be constructed via PDA
ifkr such a trash example
why did we devide u vxy and z in that manner?
Could also devide it so that u, vxy and z are equally long?
I always struggle with deviding it cause idk how
ok I guess i asked the wrong thing.
obviously the boundary comes from the numbers of symbols in a word.
And I guess if we check for case 1 we need to take any boundary and make vxy max. as long as the boundary itself.
But could I also say Ill make my vxy 11111 instead of 111 as in the example ? The result would be the same obviously but is that still possible?
oh damn and again I found the answer myself xD we can choose the length as long as its
pls any one can explain how to divide the uvxyz
if any one case satisfies all 3 conditions then it will be context free or not?
Sorry. If any one case satisfies all 3 conditions then we cannot say whether it is context free or not. Only if no case satisfies all 3 conditions can we say that it's *not* context free. The video is actually wrong about this. :S
Nice
There is no need of doing it for 5 case right??...2 or 3 cases would be sufficient i guess
8:22
you only need 1 case because uvxyz are all 0 .
Prove at least one of the cases it's enough or I have to discuss each one ?
all cases
@@abhayagarwal7103 why all cases?? Why not only one case??
JACK
WRONG, you cannot specify any P. 100% no points in an exam \ exercise for doing it like that.
Absolutely hate this subject...
This way of proofing is useless
Well, I got full credit on my homework using this approach. That means something.
T_T, prof this which i got in my exam
0^(2p+1)^2
Then you’ll see why it’s useless
plz this video upload in hindi language in channel
are we suppose to check for each case possible?.....can't we just conclude for any one case that it is not context free .....?
not sure but apparently if one check fails, you cant conclude anything, you cannot be sure if its context free or not, so have to do all cases