thank you and the people who have pointed out that the proof was incorrect. your videos still helped me understand what the f is a pumping lemma and what exactly I need to prove and how it works, so I'll just refrain from assuming the length of P in the proof. I had no chance of ever understanding this just by reading our professor's material. theory of computation is complex and abstract enough on its own, so it's twice as important to explain this subject consistently, little by little and in simple terms
I went through almost all the pumping lemma videos here on ytube and I was like "Will I ever be able to understand pumping lemma?" but this and other two pumping lemma vids of yours saved me. Seriously, you explained soo well..thank you thank you! :) :D
@@karanparmar1553 you are right, because the pumping length is universal, and universal variables cannot be assumed they must be proven from an arbitrary point. The string however can be assumed because it is existential.
You got an amazing talent of explaining the concepts in such an easy and detailed way. Thank you. Please can you give some more examples of pumping lemma. The concept is clear but still having some doubts when it comes to another questions of proving languages not regular.
Great video as usual. But in the beginning of this video it isn't clearly explained why 0101 cannot be stored by a Finite State machine. Yes FS machines can store memory, but only FINITE amounts of memory. 0101 CAN be stored in an FS, but the problem is that yy can equal 0101, 00110011, 11001100, ..., etc. because each y is a word that is an element of the Kleene closure of the alphabet of {0,1}. This means that each y can equal a string of infinite length and THATS why it can't be stored in a Finite State machine.
The Kleene closure can be of infinite size but its strings cannot have infinite length just as there can be infinite integers but every integer by itself is finite. So y cannot equal a string of infinite length
no you are wrong,fs only known his current state ,it cant store and also dont know how many or what amount of input given in it to reach that state.it only recognize pattern through logic ,cant count input or output. so it does not able to count alphabets of 0101010,.. like strings.
@archentity hello friend, this question is something our professor didn't bother to explain much and your explanation helped more in understanding exactly what strings can be accepted. I had these questions: 1) the language will not accept 0 or 1, correct? 2)Will the language accpet odd length of string, if not how did you know? and last question: what does 'yy|y' mean? should the substrings be identical when the string isbroken? what if it were 'yyy|y' then what?.
You can pick any string you want as S, any value you want for p, then break it down to xyz in any way you want, and pick any value you want for i. You simply need to find ONE string where you do those steps (S -> p -> xyz -> i) such that the newly formed string with the incremented i is NOT in A. S must use P, so your S cannot be the finite "001001" for example. And all values of P must result in a valid string for S to exist in A. For example, S=0p10p1 as in the video, will always exist in A no matter the value for P. However, If you pick (01)^p as your string, consider p = 3. The resulting string 010101 is NOT in alphabet A, as we're looking for two sequences duplicated, not 01 iterated. When we cut the string in half and see 010 and 101 are not same, so S=(01)^p is NOT a member of A, and not a legal choice for proof. We can't try S=0p because if P is odd, then S is not a member of A (ex: 000 cannot be described by {yy}). But to show how a different proof can work, let's try S=0p0p and P = 4 S = 00000000 = xyz We can break it down in any way such that |xy|
@@XoIoRouge Thank you for explanation, especially showing a different solution rather than 0^p10^p1 When adjusting the xyz values I think we always have to make sure that the conditions |y|>1 and |xy|
@@jamescommon478 Oof, it hurts to not have used the knowledge I gained since I posted this (RUclips seems to be rounding down the length of time since I posted, I last used this knowledge roughly 2 years ago or more). I reread my post and even rewatched the video, but I don't recall exactly the proper calculations. Dang. I *believe* the answers to be: 1. Yes, you're correct, you must have |y|>1 and |xy|
Just to clarify to any person watching this. He chooses 7 as , but when you prove (disprove) something using the pumping lemma, you don't even need to choose any number. Your answer can be completely theoretical.
My understanding is that choosing xyz is up to you in order to see whether or not the pumping lemma holds. If you divide S in a way that doesn't satisfy the xy length condition, then you know you don't have a regular language. But someone should correct me if I'm wrong...
If the language isn't regular, then how do you determine what kind of language it belongs to? There are four types of languages in the Chomsky Hierarchy.
it should not be too long or too short, like the length that is sufficiently large enough to cover a wide range of strings in the language. In the previous video sir took pumping length as 7.
This proof is incomplete and thus incorrect. He must show that _no matter which x-y-z split you choose,_ one of the 3 conditions is broken. It was not enough to arbitrarily set P=7, x=00, y=0000, z=0100000001.
@@parasmittal3697 No, you have to prove that you cannot find split that will satisfy it. He only proved that he found one split that did not satisfy it.
@@tomashorych394 for proving something regular we need to prove for a general case but if we have even one example for which it is irregular we can say that its irregular , prof might not consider it though 😂
@@tomashorych394 It really doesn't matter which value of P it takes cause no matter how you split your string for i > 1 you will always get a string that doesn't belong to the Language given originally, so proofing it using an example is just something to help give an understanding of why it is not a regular language
He explains at 6:52 that one of the conditions is |xy| 0, lets say 3 zeros, followed by the middle 1 and say 2 more more zeros, then |y| =6. Since we took 3 zeros from the left side of the this means that |x| is 4, because p=7 and 7-3=4. Now if we add the |x|+|y|=|xy|=4+6=10 and 10 > p. This breaks the condition that |xy|0. Hope this helps!
So from what I gathered it appears P and the values of X, Y and Z are chosen arbitrarily without their being any rhyme or reason behind this. Can you please clarify?
You assume that L is regular. If you find one example where the pumping Lemma isn't working, you have shown, that L isn't regular. It's the same as if say for every x is true that f(x) = 2x is always 0. But if you find one example that it isn't one, you have show my assumption is false.
Agreed. P needs to be generalized... Setting P=7 invalidates this proof as the pumping lemma only requires that for some p the conditions are true. What about p=8? What about p=9?...
Eduardo Macedo says: You can take whatever form you want provided that it belongs to the language you are trying to show that it's not regular. But you should try to choose one that makes it easier to find a string that doesn't conform to the properties of a regular language. Since you are trying to prove by contradiction, you only need to find one string that does not fit the properties of a regular language.
It doesnt really matter what length of p you will choose, as long as you are able to divide the word on the three parts x(y^i)z, satisfying |y| > 0 and |xy| < p
I still don't quite get this. the lemma said "The Regular Language A has a pumping length P". So even if 7 does not satisfy the rules, how about 8, 9, 10? they could still be the valid pumping length. this is the reason i don't quite buy this proof.
The part where p is assumed to be 7 is not a part of the proof, it is there just for the clarity of the explanation. The proof would just mention p as the pumping lemma (i.e. the length that forces a loop), without atributing a specific value to it.
Tian You There's sort of an implied _proof by induction_ going on. 0^p10^p1 is a counterexample that works for any value of p. |xy| has to be less than or equal to p, and so with the case of p=7, y cannot include the "1" character, as it is at the 8th position. The first "1" will always be at the (p+1)th position for any value of p, and thus we can only ever copy the "0"'s.
when you choose p=7 and y=4, did you choose those randomly, or are those values significant? It's confusing because those were the same values you chose in the previous video.
You can take whatever form you want provided that it belongs to the language you are trying to show that it's not regular. But you should try to choose one that makes it easier to find a string that doesn't conform to the properties of a regular language. Since you are trying to prove by contradiction, you only need to find one string that does not fit the properties of a regular language.
I didn't understand why did you said that we have to prove the second and third condition to be satisfied..whereas here we have assumed A is regular and we have to show that none of the pumping conditon can satisfy as contradiction ....please someone explain me
we have to choose x, y and z such that the 2nd and 3rd conditions are true, and then prove that the 1st condition is not met and thus the language is not regular
the pumping length P is only imposed on 0 not on 1 because (0^p)1(0^p)1...in the best case, let us consider the first part (0^p)1 as xy...in this case if we include the 1 in y then |xy| i.e length of xy will become (p+1)...so by default the third condition is broken...thats why we have to take only 0s as y in this.
God bless you, my Indian friend. You are the reason I finally understood the Pumping Lemma stuff. SO MUCH better explained than in my lecture slides!
where are u from man
@@vladivostok853 Bulgaria
@@kevinstefanov2841 How you know that he is Indian?
@@aswineditz007 this is an indian channel.
accent@@aswineditz007
thank you and the people who have pointed out that the proof was incorrect. your videos still helped me understand what the f is a pumping lemma and what exactly I need to prove and how it works, so I'll just refrain from assuming the length of P in the proof. I had no chance of ever understanding this just by reading our professor's material. theory of computation is complex and abstract enough on its own, so it's twice as important to explain this subject consistently, little by little and in simple terms
I went through almost all the pumping lemma videos here on ytube and I was like "Will I ever be able to understand pumping lemma?" but this and other two pumping lemma vids of yours saved me. Seriously, you explained soo well..thank you thank you! :) :D
Hy dear .You seem to be lovely
Except this video is false lol.....you can't just assume a particalar value in a proof
@@karanparmar1553 you are right, because the pumping length is universal, and universal variables cannot be assumed they must be proven from an arbitrary point. The string however can be assumed because it is existential.
@@karanparmar1553 do you realize we are proving by contradiction....
It is best ever simplest form of explanation of Pumping Lemma for proving certain languages are Not Regular, I am glad to see this.
Exams in one week and I've noticed that my lecturer is getting all he's "teaching" us from this channel, even the exact same examples😂
Better he explained..my lecturer made slides using the screenshots from these videos 😂😂
exam in about 12 hours
Dude, I have about 2 hours
Less than 5 hr
1 hour left
after exam 😶
In exam
3:00 how did you decide the string S? And how do you decide the pumping length?
its just a number wich is not too long or too short
You got an amazing talent of explaining the concepts in such an easy and detailed way. Thank you. Please can you give some more examples of pumping lemma. The concept is clear but still having some doubts when it comes to another questions of proving languages not regular.
at 3:12 why 0^p1 0^p1, why not 01^p 01^p ?
im confused on that part too, can someone explain, it been 3 years
@@loveurselfilm yea me too man
@@loveurselfilm same doubt
@@abhisheksheokand8064 hey me to
@@loveurselfilm me too man. Help please
Great video as usual. But in the beginning of this video it isn't clearly explained why 0101 cannot be stored by a Finite State machine. Yes FS machines can store memory, but only FINITE amounts of memory. 0101 CAN be stored in an FS, but the problem is that yy can equal 0101, 00110011, 11001100, ..., etc. because each y is a word that is an element of the Kleene closure of the alphabet of {0,1}. This means that each y can equal a string of infinite length and THATS why it can't be stored in a Finite State machine.
The Kleene closure can be of infinite size but its strings cannot have infinite length just as there can be infinite integers but every integer by itself is finite. So y cannot equal a string of infinite length
no you are wrong,fs only known his current state ,it cant store and also dont know how many or what amount of input given in it to reach that state.it only recognize pattern through logic ,cant count input or output. so it does not able to count alphabets of 0101010,.. like strings.
He didn't go in details because it's already explained in his previous videos.
@archentity hello friend, this question is something our professor didn't bother to explain much and your explanation helped more in understanding exactly what strings can be accepted. I had these questions: 1) the language will not accept 0 or 1, correct? 2)Will the language accpet odd length of string, if not how did you know? and last question: what does 'yy|y' mean? should the substrings be identical when the string isbroken? what if it were 'yyy|y' then what?.
sir i have a doubt in this example you took 0 power p and 1 .why did'nt you took (01) whole to the power p. please explain.
You can chose any such string that lies in A
You can pick any string you want as S, any value you want for p, then break it down to xyz in any way you want, and pick any value you want for i. You simply need to find ONE string where you do those steps (S -> p -> xyz -> i) such that the newly formed string with the incremented i is NOT in A. S must use P, so your S cannot be the finite "001001" for example. And all values of P must result in a valid string for S to exist in A. For example, S=0p10p1 as in the video, will always exist in A no matter the value for P.
However, If you pick (01)^p as your string, consider p = 3. The resulting string 010101 is NOT in alphabet A, as we're looking for two sequences duplicated, not 01 iterated. When we cut the string in half and see 010 and 101 are not same, so S=(01)^p is NOT a member of A, and not a legal choice for proof.
We can't try S=0p because if P is odd, then S is not a member of A (ex: 000 cannot be described by {yy}).
But to show how a different proof can work, let's try S=0p0p and P = 4
S = 00000000 = xyz
We can break it down in any way such that |xy|
@@XoIoRouge Thank you for explanation, especially showing a different solution rather than 0^p10^p1
When adjusting the xyz values I think we always have to make sure that the conditions |y|>1 and |xy|
@@jamescommon478 Oof, it hurts to not have used the knowledge I gained since I posted this (RUclips seems to be rounding down the length of time since I posted, I last used this knowledge roughly 2 years ago or more). I reread my post and even rewatched the video, but I don't recall exactly the proper calculations. Dang.
I *believe* the answers to be:
1. Yes, you're correct, you must have |y|>1 and |xy|
@@XoIoRouge Will be glad. Thanks a lot for your attention. All the best for you
Just to clarify to any person watching this. He chooses 7 as , but when you prove (disprove) something using the pumping lemma, you don't even need to choose any number. Your answer can be completely theoretical.
Thank you!
Too easy methodology of teaching like your way of teaching!
very nice explanation about the relation between "memory" and the limitation of finite state machines.
What is the procedure of deciding the number of x y and z. How do we select that these 4 zeroes are y and starting 2 is x and rest is z
You can split it anyway. Just need to find a splitting that works. In his example most splits will work.
Do we have to show all 3 cases compulsorily or is one case where it proves it is not regular is enough?
7:29 I was a bit confused. If you add one more 0 in X does that not make |xy| 7 which is =
Can anyone explain me is there any criteria for dividing S into xyz? Can we randomly divide S into three parts?
My understanding is that choosing xyz is up to you in order to see whether or not the pumping lemma holds. If you divide S in a way that doesn't satisfy the xy length condition, then you know you don't have a regular language. But someone should correct me if I'm wrong...
How do we decide what value to be taken for 'i'? for some examples 'i' is taken as 0 and for some its taken as 2.. so do we pick it randomly?
thank you so much for teaching me pumping lemma!!!
why the S = 0 raise to the power p and 1 specifically and not S = 01 raise to the power p like you did in previous lecture?
In |xy|
When adjusting the xyz values I think we always have to make sure that the conditions |y|>1 and |xy|
neso acedamy you are moments away from 100k subscribers
Congrats .
Million now hehe
2.5million now hehe😂
amazing! thank you so much for the clear explanation!
Ur teaching is simply awesome...ur videos gives me confidence to do other problems in theory of computation
Is there any condition to take the values of y and length of y. Why do you take it y length as 4. Kindly clarify me.
you can divide it as u please. as long as y is in the middle of x and z, the length of it doesnt really matter
You can y length as much as u want granted that |xy|
this channel is just way too good
4:39 do we have to cover always 4 digits for y?
Great tutorial! thank you!
If the language isn't regular, then how do you determine what kind of language it belongs to? There are four types of languages in the Chomsky Hierarchy.
What if i decide that p=15? What are the rules to choose the value of p?
it should not be too long or too short, like the length that is sufficiently large enough to cover a wide range of strings in the language. In the previous video sir took pumping length as 7.
This proof is incomplete and thus incorrect. He must show that _no matter which x-y-z split you choose,_ one of the 3 conditions is broken. It was not enough to arbitrarily set P=7, x=00, y=0000, z=0100000001.
for proving something is not regular even one example is enough .
@@parasmittal3697 No, you have to prove that you cannot find split that will satisfy it. He only proved that he found one split that did not satisfy it.
@@tomashorych394 for proving something regular we need to prove for a general case but if we have even one example for which it is irregular we can say that its irregular , prof might not consider it though 😂
@@parasmittal3697 No, for proving something irregular you still have to prove for a general case of a split.
@@tomashorych394 It really doesn't matter which value of P it takes cause no matter how you split your string for i > 1 you will always get a string that doesn't belong to the Language given originally, so proofing it using an example is just something to help give an understanding of why it is not a regular language
Why not taken cases that Y lies in RHS part..middle part ..LHS part..
Like in previous one...
a^n b^n
would they be required here too? could someone please answer this, would really appreciate it!!
If you prove it for one Part and the Language is not Regular, why would you test the other Parts too? :)
He explains at 6:52 that one of the conditions is |xy| 0, lets say 3 zeros, followed by the middle 1 and say 2 more more zeros, then |y| =6. Since we took 3 zeros from the left side of the this means that |x| is 4, because p=7 and 7-3=4. Now if we add the |x|+|y|=|xy|=4+6=10 and 10 > p. This breaks the condition that |xy|0. Hope this helps!
@@RogueAgent711 yes you are right, but if you see the first video he mad at 12:24 he said that the lenth of |xy| should be
If it is {0,1}* we can also take Y= 0^P 1^P
that means S can also be
S= 0^P 1^P 0^P 1^P
Correct me if iam wrong?
Same question though
Note : At last condition checked, it should be checked |xz|
Thank you so much!
So from what I gathered it appears P and the values of X, Y and Z are chosen arbitrarily without their being any rhyme or reason behind this. Can you please clarify?
p =7
the message is clear
Thala for a reason 😛
Informative lecture
Exam in about 30 mins 👍👍👍
Exam about next morning...now it's 12.44 am😂
So effectively if i is large enough, then the suffix will have two 1s but the prefix won’t
sir can you please add again more videos for remaining topics like Turing machine and etc.
WHY HE HAS USED ONLY 1 CASE TO PROOF IS IT OK TO PROVE WITH 1 CASE ONLY......
You assume that L is regular. If you find one example where the pumping Lemma isn't working, you have shown, that L isn't regular. It's the same as if say for every x is true that f(x) = 2x is always 0. But if you find one example that it isn't one, you have show my assumption is false.
He explains at 6:52 , if you choose y that contains 1's you will not fulfill the second condition of the lemma
@@ron5101 why so
@@kunaljha2393 If he uses the other condition i.e. ...010... as y, then it automatically fails the last test which is |xy|
Agreed. P needs to be generalized... Setting P=7 invalidates this proof as the pumping lemma only requires that for some p the conditions are true. What about p=8? What about p=9?...
thank you, the video is great
in previous question you had given a^nb^n so you considerd a^pb^p but in this question there is no power then why are you considering 0^p1
Eduardo Macedo says:
You can take whatever form you want provided that it belongs to the language you are trying to show that it's not regular. But you should try to choose one that makes it easier to find a string that doesn't conform to the properties of a regular language.
Since you are trying to prove by contradiction, you only need to find one string that does not fit the properties of a regular language.
@@gyatso_fam Thank you for clarifying. Helped me understand the problem!
In this example there is only 1 case but in previous example there were 3 cases can you explain that? And thanks a lot for teaching me TOC.
Sir agar ek variable me hoga toh kaise solve krenge coz aapne jo q. Btaye hai vo 2 variable either a or b or 0.1. BUT what about only a variable??
Like the new instrumental for neso academy :D
Why you take value of S to be 0^p1 instead of taking 01^p
aynen kanka ben de takıldım ona
@@cavitsevinc3963 Öyle alsa dahi bir koşul yine de sağlanmayacaktı.
why to use length of p=7 ?????
It doesnt really matter what length of p you will choose, as long as you are able to divide the word on the three parts x(y^i)z, satisfying |y| > 0 and |xy| < p
I still don't quite get this. the lemma said "The Regular Language A has a pumping length P". So even if 7 does not satisfy the rules, how about 8, 9, 10? they could still be the valid pumping length. this is the reason i don't quite buy this proof.
The part where p is assumed to be 7 is not a part of the proof, it is there just for the clarity of the explanation. The proof would just mention p as the pumping lemma (i.e. the length that forces a loop), without atributing a specific value to it.
Tian You There's sort of an implied _proof by induction_ going on. 0^p10^p1 is a counterexample that works for any value of p. |xy| has to be less than or equal to p, and so with the case of p=7, y cannot include the "1" character, as it is at the 8th position. The first "1" will always be at the (p+1)th position for any value of p, and thus we can only ever copy the "0"'s.
Thank you so much sir....
Why u take four value of Y in every question is it compulsory or we can take whatever we want?
please sir do more videos on this topic the topic is not clear within two examplle
how we are taking x,y,z values as x=oo and y=0000 and z=0100000001 ? please explain
those are values which you can choose
when you choose p=7 and y=4, did you choose those randomly, or are those values significant? It's confusing because those were the same values you chose in the previous video.
if u know the ans let me know
You can assume any y and p such that your assumption should dissatisfy the 3 condition that are used to prove language as non- regular.
can i choose the value of P some other numbers except 7... what is the criteria for choosing P?
Yeah u can choose any value of p
except 0
very well done.. thanks... it is really awesome...
ibany indus, {0,1}* means 0^p 1^p, not 0^p 1
0^p 1 is a member of {0,1}*
you shouldnt take p=7,you should proof that A is not regular for every value of p,not just one example 7,this is not correct
how do you decide that above which we have to put the p as a power????
please reply fast tommorrow is my exam
How can i understand, the meaning of "yy" ? ..
Sir x ki anni values y ki anni values tisukovalli ani alla telusthundhu sir ante divide chestham kadha sir eq is alla tisukuntaro Chepadi sir
why there is any 2nd and 3rd cases like the previous vedio?
how to choose the string i am not getting how to choose
can anyone explain the meaning of (0,1)*
Thanks
God bless you , I finally understood this fucking subject
If (01)* is represented by {0, 1}* in set theory. Then how would I represent (0 + 1)* in set theory
Can we take pumping lemma P value any number ?
Thank you sir
Sir. Why you always take a length of p=7 ?????
why 0^p only y cant we take 1^p ??
You are exactly right babe
You can take whatever form you want provided that it belongs to the language you are trying to show that it's not regular. But you should try to choose one that makes it easier to find a string that doesn't conform to the properties of a regular language.
Since you are trying to prove by contradiction, you only need to find one string that does not fit the properties of a regular language.
At 3:00 , how do we decide the string..?
Thankyou sir
Thank you
1 word- Clutch
Can I take the string as 1*0 1*0
Thank you..
Can i divide xyz in any order??
I didn't understand why did you said that we have to prove the second and third condition to be satisfied..whereas here we have assumed A is regular and we have to show that none of the pumping conditon can satisfy as contradiction ....please someone explain me
we have to choose x, y and z such that the 2nd and 3rd conditions are true, and then prove that the 1st condition is not met and thus the language is not regular
But I thought that the language is not regular if any of the conditions are not met depending on how you divide S up into xyz...
@@az100eletronics12 nope, all three conditions are to be satisfied...
How to consider pumping length 7
thanks
Why pumping length is 7 ? I have doubt
it is very helpful
Thank you :D
can anyone please tell me what does the * mean in the question?
0 or more than 0
How to choose x y and z
Closure is both on 0&1 then why u take only 0
doubt:why you took p on to the zero why not on to the 1.
If A={yy|y belongs to {a,b}} is regular or not?
It is not regular, because a regular language automata dont have any memory to remember, if the first y is equal to the second one.
it is regular bro bcz you can draw a DFA for the following as A have only { a,b,aa,bb} as string.
thankyou sir
Sir please upload Microprocessor 8085
Can we keep the zeros as they are, and the length seven of the 1s? like this 100000001000000.......?
Exam is in 2 hrs.
Thank you so much.
you ready for the 334 today fellow stevens student
hahahaha
Why cant we choose 0^p0^p? Someone please explain :(
You can choose A=0^p 0^p
Then ,
We will have one case y=0^k where |k| contradiction
sir plz upload video for PDA and Turing machine, as soon as possible.
why 7 is the pumping number
The lecture was great but i quite didn't understood what you were saying about taking the value of y in the end to satisfy the IxyI
Yes please can someone explain this
the pumping length P is only imposed on 0 not on 1 because (0^p)1(0^p)1...in the best case, let us consider the first part (0^p)1 as xy...in this case if we include the 1 in y then |xy| i.e length of xy will become (p+1)...so by default the third condition is broken...thats why we have to take only 0s as y in this.
If anybody knows which string will be accepted if its given like (0+1)*
Exam in 8 hours
Unit 3,4,5 still remaining. Wish me luck🤞