I think another approach to this question to make it more understandable to solve would be: - When partitioning w into xyz, partition such that the other 2 cases (exclude the case of pumping i >0) are also satisfied - With the cases you have (where the 2 other conditions satisfy), apply the pumping conidition i.e i = 1,2,3,4... - If any case fails then the pumping lemma fails Hope this helps.
Giving a value to P is not a correct solution for most of the University Exams and not an exact solution. Instead please give K+L+M to P. [ x=a^K, y=a^L, z=a^M+b^P ] Then when you increase the i which is on top of y, you will see that on the left side there will be L more a's according to rule |y|>0 . This is how you prove that it is not a regular language. (Case 2 and 3 are cancelled by the Rules 2 and 3. That's why there is no point to check those cases)
The part where you actually define p=7 is potentially misleading because p is just a symbolic threshold and will be useful in cases such as proofing inequalities by utilizing the 2nd and 3rd conditions in pumping lemma. So we don't necessarily need to know what is p. This example just need to use the 1st condition of the lemma to proof.
the idea is that p is an abstract length, given that length of (xy) must be equal or less of p, y can only consist of letter(a)s, since the rule is a^pb^p. howeve given y is all letter(a)s, xy^iz for all i>=0 is not in the language, thus that it is not regular for any p value
dude you fucking saved me for my final man. my teacher and tas could not teach this for their life, and your 2 videos on pumping lemmas explained what they could not explain. They had 2 and a half hours and you did it in 20 minutes. Thank you.
In case 2 |xy| = 13 and in case 3 |xy| = 9 which violates the condition of pumping lemma which states that |xy| should be less than of equal to pumping length ( here 7 )
since |xy|>P (P=7) in case 2 and case 3,they are invalid divisions of S into x, y and z. So proceed using case 1 only(there is only one way to divide S into x, y and z).
In the 2nd and 3rd case you have broken 2th PL rule. I would recommend to use some parameters, not numerical values F.E. case 2: Let say, that PL length is just p; So, we chose the next string: a^p.b^p. x = a^t.b^s y = b^n z = b^i The 2nd rule of PL tells, that |xy|
How do you know to which category the pumping string belongs to? I mean, if we give a counter example for one case, we assume that the pumping string 'y' contains only a's. But we cannot be sure of that. What if the pumping string contains only b's (or) contains a mixture of both a's and b's. That is why we have to give a counter-example for all possibilities
Thanks Neso academy for making me more confuse then I already was,The funny part is my cute little lecturer also followed this video and guess what, even he don't know why he assumed pumping lemma p=7 same as you
Case 2 and case 3 are wrong. In these cases, |xy| is being grater than p, which is not possible. Case 2 and 3 would be possible is we would have taken the S something else like a^4 b^4 etc.
I think yes, the point is just for finding a y that cannot be satisfied. Btw, I think in case 3, no matter how you choose the y string, the condition 3 |xy|
Thanks a lot for this video. One thing I don't get is the divide S part. Can you decide as u want or is there any rules for dividing or spliting into xyz strings? You mention there three cases: case 1: aaa aaaa bbb bbbb -> why does x has two a's and y four a's instead x has one a and y has 6 a's and z has all b's? x= aa y=aaaa z= abbb bbbb case 2: aaa aaaa bbb bbbb -> why do you split like this? Is there any reason? x = aaa aaaa bb y = bbbb z = b case 3: aaa aaaa bbb bbbb -> why do you split like this? Is there any reason? x = aaa aa y = aabb z = bbbb Thanks a lot for you answer
Bit late for this one, but yes, you may as long as it matches the case e.g. in the example a^n b^n. So it says case 1, a belongs in y; you could even have it so the substring x is empty e.g.: take p as 7: x=ϵ y=aaaaaaa z=bbbbbbb to verify the case: take i as 2 therefore we double the amount of a's => x=ϵ y=aaaaaaaaaaaaaa z=bbbbbbb still this is broken as number of a's should equal number of b's However, at any point the y substring may not be empty as it would break the rule that |y| > 0. Hope it helps!
@@TheFixieGuy This is not correct! We need to use make sure that all the theorem are "true" first in order for us to "use" the pumping lemma, if the conditions aren't true then that means that we cannot use the pumping lemme on that specific string in the first place
Neso Academy : Asks to go check out the previous video to view the theory. Also Neso Academy : Proceeds to show contents of previous video to solve example...
pumping lemma is a very broad and complicated topic; its really nice that you go into detail with the specific cases, but i think you should explain that the proof is not complete at the state you left it at; you only proved it for a specific P, and a specific length for Y. The video is great for forming intuition, but not a perfect step by step guide for proofs
00:03 Example of proving a language is not regular using Pumping Lemma 01:31 Proving regularity using Pumping Lemma 03:02 Introduction to Pumping Lemma for Regular Languages 04:54 Explanation of dividing a string into three parts 07:14 Explaining the division of string into parts XY and Z 09:20 Counting S and B occurrences for regular language verification 11:02 Pattern mismatch leads to not being regular 12:43 Pumping Lemma shows language is not regular
If we set the pumping length to 7, S may be aaaabbbb, aaaaabbbbb, aaaaaabbbbbb, etc. Since we are proving the language A is not regular by contradiction, we only need to find one counterexample. The lecturer just selected aaaaaaabbbbbbb. Hope this reply may help someone who gets confused.
I think that you can't use only p=7. Maybe this language is regular but it requires more than 7 states to be able to pump. This should be prooved with arbitrary p.
please upload more video on context free grammer. and also upload about drawing a finite automata from context free grammers. thank u so much your video is helpful
All are ok but case no 3 seems mistake because here no of a=no of b after spliting s and again counting . so here its a regular language and you skipped counting of no of a and b in this case. pls check it sir... thank you a lot...
for people reading this now, it doesnt matter how many y's and x's you take in y aslong as it is less then the pumping length which he choose is 7. Case 2 and 3 he just proved it but before he even pumped it fails condition 2. Why? Because in order for you to even take b's for y x would have to be all of the a's so even if you took 1 b as y or 2 b's as y. No matter how many you take it will be over the pumping length but he just pumped it to prove it still is not regular. Samething goes for when y is in ab you can take 1a and 1b still have to take 6 a's and you will have a length of 8! Good luck every1 this class sucks dick
But the rule says to show that none of the cases satisfies all three conditions at the same time. But case 1 clearly satisfies all three conditions at the same time. So how is it not.regular
Just to clarify things. the explanation is correct in the sense that he checks for the |xy|
Thank you!
same my teacher was mad lol I couldnt use this proof metho
I think another approach to this question to make it more understandable to solve would be:
- When partitioning w into xyz, partition such that the other 2 cases (exclude the case of pumping i >0) are also satisfied
- With the cases you have (where the 2 other conditions satisfy), apply the pumping conidition i.e i = 1,2,3,4...
- If any case fails then the pumping lemma fails
Hope this helps.
I think we are not suppose to proof second and third condition as |y| >0 & |xy|
exactly.... I just doubted this and came to check comments
Here y is greater than 0 then how it will be proved
If ynot greater than 0 thenonly it will be proved
Exactly
Giving a value to P is not a correct solution for most of the University Exams and not an exact solution. Instead please give K+L+M to P. [ x=a^K, y=a^L, z=a^M+b^P ] Then when you increase the i which is on top of y, you will see that on the left side there will be L more a's according to rule |y|>0 . This is how you prove that it is not a regular language. (Case 2 and 3 are cancelled by the Rules 2 and 3. That's why there is no point to check those cases)
The part where you actually define p=7 is potentially misleading because p is just a symbolic threshold and will be useful in cases such as proofing inequalities by utilizing the 2nd and 3rd conditions in pumping lemma. So we don't necessarily need to know what is p. This example just need to use the 1st condition of the lemma to proof.
Thank you! I lost 15 points because of this in my midterm.
the idea is that p is an abstract length, given that length of (xy) must be equal or less of p, y can only consist of letter(a)s, since the rule is a^pb^p. howeve given y is all letter(a)s, xy^iz for all i>=0 is not in the language, thus that it is not regular for any p value
The pumping lemma was pumping me because my professor didn't teach it well. However you taught this so well thanks!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
dude you fucking saved me for my final man. my teacher and tas could not teach this for their life, and your 2 videos on pumping lemmas explained what they could not explain. They had 2 and a half hours and you did it in 20 minutes. Thank you.
@@Kailahuwdym
In case 2 |xy| = 13 and in case 3 |xy| = 9 which violates the condition of pumping lemma which states that |xy| should be less than of equal to pumping length ( here 7 )
Ajinkya Wandale how to find the values of |xy|???
plz explain... that's the biggest confusion i am facing...
it's just how many characters are in the x part + how many characters are in the y part
since |xy|>P (P=7) in case 2 and case 3,they are invalid divisions of S into x, y and z. So proceed using case 1 only(there is only one way to divide S into x, y and z).
yes, he explains this in the video, so in two different ways those two cases(2 and 3) are not pumpable
Thank you so much, this is so much clearer than how my professor teaches the pumping lemma, great job!
In the 2nd and 3rd case you have broken 2th PL rule.
I would recommend to use some parameters, not numerical values
F.E. case 2:
Let say, that PL length is just p;
So, we chose the next string: a^p.b^p.
x = a^t.b^s
y = b^n
z = b^i
The 2nd rule of PL tells, that |xy|
I'm trying to follow your explanation but got stuck at the "t+s+n
Why we are going for case 2 and 3? They already broke the rule of |xy|
Same doubt.
How do you know to which category the pumping string belongs to? I mean, if we give a counter example for one case, we assume that the pumping string 'y' contains only a's. But we cannot be sure of that. What if the pumping string contains only b's (or) contains a mixture of both a's and b's. That is why we have to give a counter-example for all possibilities
Thought the same. We had to divide it right first
agreed
@@aravindm5061 but, It doesn't satisfying case 2, 3
Thanks Neso academy for making me more confuse then I already was,The funny part is my cute little lecturer also followed this video and guess what, even he don't know why he assumed pumping lemma p=7 same as you
🤣🤣 My lecturer is also following the same video.
At 6:40 |XY|
correct, not even case 3
i think that's the point.
Point !
It confused me. Case 2 and 3 don't satisfy the condition |xy|
Please continue doing this great work sir ...it means a lot..
Case 2 and case 3 are wrong. In these cases, |xy| is being grater than p, which is not possible. Case 2 and 3 would be possible is we would have taken the S something else like a^4 b^4 etc.
Thanks for making me more confused than I already was!
Ur a f***** man then
Is there a reason that we are choosing y to be length of 4 for all of the cases?
Also: for case 3 can y = aaab?
I think yes, the point is just for finding a y that cannot be satisfied.
Btw, I think in case 3, no matter how you choose the y string, the condition 3 |xy|
L={a^i b^j c^k a^l b^m c^n | i>=3, j>=1, k>=2, l is an even number, m is odd no and n is any number divisible by 3 }
Plz make video for this.
This is great, thank you. I now understand how the pumping lemma works.
Thanks a lot for this video. One thing I don't get is the divide S part. Can you decide as u want or is there any rules for dividing or spliting into xyz strings? You mention there three cases:
case 1: aaa aaaa bbb bbbb
-> why does x has two a's and y four a's instead x has one a and y has 6 a's and z has all b's?
x= aa
y=aaaa
z= abbb bbbb
case 2: aaa aaaa bbb bbbb
-> why do you split like this? Is there any reason?
x = aaa aaaa bb
y = bbbb
z = b
case 3: aaa aaaa bbb bbbb
-> why do you split like this? Is there any reason?
x = aaa aa
y = aabb
z = bbbb
Thanks a lot for you answer
Bit late for this one, but yes, you may as long as it matches the case e.g. in the example a^n b^n. So it says case 1, a belongs in y; you could even have it so the substring x is empty e.g.:
take p as 7:
x=ϵ
y=aaaaaaa
z=bbbbbbb
to verify the case:
take i as 2 therefore we double the amount of a's =>
x=ϵ
y=aaaaaaaaaaaaaa
z=bbbbbbb
still this is broken as number of a's should equal number of b's
However, at any point the y substring may not be empty as it would break the rule that |y| > 0.
Hope it helps!
@@jiaxuanng2396 tqsm
The moment you give a fixed value to P, the theorem proves nothing. Also the cases 2 and 3 make non-sense, since they violate the constraint |xy|
How do we assume "p"? Like are there any rules for that or we can assume p
Pls reply
i can not afford to buy paid your course. i am in 3rd sem now btech. pleaseeeeee dont remove these lectures. its is extremely helpfull
in the case 2: |XY| = 13 which is a violation of theorem as |XY|
it is not a mistake. if the language was regular, |XY|
@@TheFixieGuy This is not correct! We need to use make sure that all the theorem are "true" first in order for us to "use" the pumping lemma, if the conditions aren't true then that means that we cannot use the pumping lemme on that specific string in the first place
@@STxFTW true
Neso Academy : Asks to go check out the previous video to view the theory.
Also Neso Academy : Proceeds to show contents of previous video to solve example...
plz sir upload these video as fast as possible ,
Bcoz my exam is close.
how did you do in your exam? i hope you did well, brotha. good luck to your past self
@@AndyD6 backlog...
@@rj-nj3uk what is backlog? ?
@@AndyD6 it means he failed the exam lol.
pumping lemma is a very broad and complicated topic; its really nice that you go into detail with the specific cases, but i think you should explain that the proof is not complete at the state you left it at; you only proved it for a specific P, and a specific length for Y. The video is great for forming intuition, but not a perfect step by step guide for proofs
00:03 Example of proving a language is not regular using Pumping Lemma
01:31 Proving regularity using Pumping Lemma
03:02 Introduction to Pumping Lemma for Regular Languages
04:54 Explanation of dividing a string into three parts
07:14 Explaining the division of string into parts XY and Z
09:20 Counting S and B occurrences for regular language verification
11:02 Pattern mismatch leads to not being regular
12:43 Pumping Lemma shows language is not regular
how to assume pumping length?
Assumption
@@prathamthorve4524tf 😂
This is VERY transparent. Thank you.
What if this lemma doesn't satisfy for P = 7, but does so for P > 7? For P > 100? You should prove it for a general case.
For a general P,. you have to consider aaa...aa bbb...bbb with P a's and P b's.
If it failed for P=7, that simply means Language isn't regular. Then there's no point in doing the same for all the other no of P.
@@shahinshaikh07 that’s not true
You are very good at explaining things! You must know that :) Thanks for the help!
sir you can also provide the lectures notes for the particular video or the end up of the course . Its really helpful for me to learn easy manner
You are superb sir
You a hard topic incredibly simple to understand, thank you
If we set the pumping length to 7, S may be aaaabbbb, aaaaabbbbb, aaaaaabbbbbb, etc. Since we are proving the language A is not regular by contradiction, we only need to find one counterexample. The lecturer just selected aaaaaaabbbbbbb. Hope this reply may help someone who gets confused.
proving by counter example and proving by contradiction are not the same thing
I think that you can't use only p=7. Maybe this language is regular but it requires more than 7 states to be able to pump. This should be prooved with arbitrary p.
I agree, the 7 here should be used just as an illustration, but the proof must be for an arbitrary p
@@rayanzakariahassici1936 but why isn't one contradiction enough?
I've watched a lot of videos and read through a lot of books, but this is the first time I really understand pumping lemma
please upload more video on context free grammer. and also upload about drawing a finite automata from context free grammers. thank u so much your video is helpful
V good method of delivering Knowledge
Sir how to select Y in a&b part?
Wonderfull explanation..
Thank you, I read my lecture 3 times and it seamed so confusing and complicated. You make it look so easy just in 14 min. Thanks again!
why u assume 7 in that pumping leagnth
Why not😂
i wanna know too. whats to stop me from assuming p =1?
Sir course is no doubt awesome, but the background music at the end is🤌🤌🤌
Very nice example and very nicely explained. Thanks !
Can anyone please elaborate on what exactly is meant by pumping length? Examples would be appreciated.
The condition 3 for pumping lemma is not satisfied can we still continue for proving it like this as explained!!???
the length of xy in case 2 is greater than p
but you earlier stated that the length of xy should be less than or equal to p
Bro thats why it is not regular
Amazing explanation, does the choice of P matter? Thanks again!
Nope
It matters if you havent reached the minimum pumping length, you can choose any value including and over the minimum pumping length
11:26 a=9,b=9 so why xy²z is not belongs to A it satisfy the condition please reply sir🙏🙏🙏🙏🙏🙏
Because it doesn't follow the pattern of a^n b^n
Sir, Can we assume P (also length of x,y and z)as any arbitrary number or is there any condition to choose? where P, |x|, |y| and |z| > 0
so.... why 7? How do we choose p?
Helpful and easy to understand
thanks Sir please complete for us the course
In case 2 and 3 the |xy| is not less than or equal to pumping lenght 7. Im confused 7:41
Sir, In case 1
There should be 16a
Because we choose y=4 and we have to square the value of i.
There should be only 8a - the exponent is special operation over strings
All are ok but case no 3 seems mistake because here no of a=no of b after spliting s and again counting .
so here its a regular language and you skipped counting of no of a and b in this case.
pls check it sir...
thank you a lot...
what if it were a^n*b^m instead of a^n*a^n?
How we divide the string in the 3 parts ... how you choose the length of X,Y&Z..?
for people reading this now, it doesnt matter how many y's and x's you take in y aslong as it is less then the pumping length which he choose is 7. Case 2 and 3 he just proved it but before he even pumped it fails condition 2. Why? Because in order for you to even take b's for y x would have to be all of the a's so even if you took 1 b as y or 2 b's as y. No matter how many you take it will be over the pumping length but he just pumped it to prove it still is not regular. Samething goes for when y is in ab you can take 1a and 1b still have to take 6 a's and you will have a length of 8! Good luck every1 this class sucks dick
Same doubt
That is so stupid, i can choose "length of 3 will be in my language" and following the instructions, I will not have a string in my language
Nyc vedio...Easy to understand...ty
Why having 4 'a's initially when you raise 'a' to the power of 2 you write 8 'a's instead of 16?
In string math, the power means that we are just concatenating. If power is 2, concatenate twice, if power is three, concatenate thrice
abi cok iyisin ahmet hoca slayta hic boyle koymamis
İngilizce bilenler için pahabiçilmez bir kaynak. İyi ki varsınız lan.
case 2 is not possible because length of xy is not less than 7
There might be a possibility that one of the three cases may satisfy xy^iz then should we consider regular or not regular
Great Sirji
Thanks a Lot
Such a nice explanation.
THANK YOU SO MUCH!! YOU ARE THE BEST!!
Hey lenght of xy should be less than equal to p
When adjusting the xyz values I think we always have to make sure that the conditions |y|>1 and |xy|
Regarding your statement 1: Yes
Statement 2 : p could be any number, you can take it as 1, or 1 billion
What if one the three is equal to p sir
What is pumping length? How it is 7 in our case....??? Waiting for reply
You just saved my life, thanks!
He crushed it rather.
LOVE IT! Thank You So Much Sir!
how did you split up x y and z
It is the first time I've seen this in Neso's videos. The explanation is incorrect!!!!
Why?
Yes...
Because he is showing 2 cases in which obviously |xy| fails to be less or equal to P
It's correct
@@ljdash9144 if those 2 cases gets correct then it is regular...
Be careful doing proofs like this on an actual assignment. I lost points because I assumed a value for P
What approach should we take then? :E
@@rujin6259 just prove it for general P
Exam se ek din pehle sab yahi discuss kar rahe hain. "Yeh pumping lemma kis bakre ka naam hain..".
But the rule says to show that none of the cases satisfies all three conditions at the same time. But case 1 clearly satisfies all three conditions at the same time. So how is it not.regular
When checking for the property |xy|
You forgot to reject your first assumption by the end , "by contradiction A is not regular language".
Well explained ❤️ thank you ❤️
sir can we say if any 1 of 3 conditions is violated then language is not regular
Is case 2 and 3 the length of xy is not less than or equal to pumping length. Then why are you taking it like that?
i love you thanks for the amazing explanation! better than my professor!
Case 2 and case 3 are not applicable in the pumping lemma method since |xy| > P. Very misleading.
if only i can get my bachelors in cs by watching all ur videos
if we are proving 3 case that all 3 conditions are true or not then if case 1 satisfy |XY|
sir please i request you to Complete your reasoning and aptitude series lectures...please as soon as possible
They call me the pumping LLama
but in case-3 get equal no.of a's and b's ...?
what abount |y| > 0 ?
how to take x ,y, z conditions in a string
In case 2 and 3 |xy|
finally someone noticed it, also he didn't explained how to choose min pumping length
Nice Sir 😊
AKTU?
I don't understand how you divide the xyz
How do you know that P isn't greater than 7?
What is the logic of dividing s=xyz?