Pumping Lemma (For Regular Languages) | Example 2

[@kevinstefanov2841]

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!

[@vladivostok853]

where are u from man

[@kevinstefanov2841]

@@vladivostok853 Bulgaria

[@aswineditz007]

@@kevinstefanov2841 How you know that he is Indian?

[@darkseid1358]

@@aswineditz007 this is an indian channel.

[@daskurabiye]

accent@@aswineditz007

[@Alisi0110]

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

[@znsxoli]

[@adityatripathi2800]

Hy dear .You seem to be lovely

[@karanparmar1553]

Except this video is false lol.....you can't just assume a particalar value in a proof

[@fallensach]

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

[@fasterbaiter]

@@karanparmar1553 do you realize we are proving by contradiction....

[@sychik8871]

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

[@ngdharashive]

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😂

[@nazeebshaik933]

Better he explained..my lecturer made slides using the screenshots from these videos 😂😂

[@jaspreetKaur-fm9jd]

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.

[@fridaaa0]

3:00 how did you decide the string S? And how do you decide the pumping length?

[@verbesserungslos1033]

its just a number wich is not too long or too short

[@rameshbakshi198]

exam in about 12 hours

[@prasantamurmu1988]

Dude, I have about 2 hours

[@bhuvanjain7001]

Less than 5 hr

[@devuslee3219]

1 hour left

[@nrk363]

after exam 😶

[@gauravdadwal5047]

In exam

[@legend7890]

at 3:12 why 0^p1 0^p1, why not 01^p 01^p ?

[@loveurselfilm]

im confused on that part too, can someone explain, it been 3 years

[@samuelgulliver886]

@@loveurselfilm yea me too man

[@abhisheksheokand8064]

@@loveurselfilm same doubt

[@topcubasov8942]

@@abhisheksheokand8064 hey me to

[@gokdenizdincer2767]

@@loveurselfilm me too man. Help please

[@leo_1487]

very nice explanation about the relation between "memory" and the limitation of finite state machines.

[@ajmalkhaniit]

Too easy methodology of teaching like your way of teaching!

[@archentity]

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.

[@imanm9206]

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

[@prantobhoumik6586]

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.

[@DaiMoscv]

He didn't go in details because it's already explained in his previous videos.

[@qurrat-ul-ain22]

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

[@Kabir-pj9re]

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.

[@lone_wolf7721]

You can chose any such string that lies in A

[@XoIoRouge]

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|

[@jamescommon478]

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

[@XoIoRouge]

​@@jamescommon478 Oof, it hurts to not have used the knowledge I gained since I posted this (KZbin 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|

[@jamescommon478]

@@XoIoRouge Will be glad. Thanks a lot for your attention. All the best for you

[@kevinparmar4827]

Do we have to show all 3 cases compulsorily or is one case where it proves it is not regular is enough?

[@utkarshmishra3343]

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

[@jondanford]

You can split it anyway. Just need to find a splitting that works. In his example most splits will work.

[@UtaShirokage]

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.

[@sanjayraju8828]

Thank you!

[@azuretang1688]

thank you so much for teaching me pumping lemma!!!

[@rgsuki999]

7:29 I was a bit confused. If you add one more 0 in X does that not make |xy| 7 which is =

[@jamescommon478]

When adjusting the xyz values I think we always have to make sure that the conditions |y|>1 and |xy|

[@asishcodes]

this channel is just way too good

[@Momeeenaaa]

In |xy|

[@palagirikeerthana1252]

Ur teaching is simply awesome...ur videos gives me confidence to do other problems in theory of computation

[@guni2285]

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?

[@gavinunrue2282]

amazing! thank you so much for the clear explanation!

[@shamanthrajreddy1230]

Great tutorial! thank you!

[@aishwaryakasthala97]

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?

[@ujjvalpatel5353]

neso acedamy you are moments away from 100k subscribers Congrats .

[@ishamaharjan4347]

Million now hehe

[@patnalaramchand2934]

2.5million now hehe😂

[@akkick7324]

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?

[@sowmocoding5740]

Same question though

[@bhuvanaprabha2809]

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.

[@heartattackingirl]

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

[@akshatkumar405]

You can y length as much as u want granted that |xy|

[@adityaarun8764]

Why not taken cases that Y lies in RHS part..middle part ..LHS part.. Like in previous one... a^n b^n

[@zacaryattack7389]

would they be required here too? could someone please answer this, would really appreciate it!!

[@javaexpertsa8947]

If you prove it for one Part and the Language is not Regular, why would you test the other Parts too? :)

[@RogueAgent711]

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!

[@hanc9973]

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

[@sinetenisinet]

Can anyone explain me is there any criteria for dividing S into xyz? Can we randomly divide S into three parts?

[@az100eletronics12]

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

[@matthewlev1342]

Thank you so much!

[@carlshod9024]

What if i decide that p=15? What are the rules to choose the value of p?

[@preshikagiri1153]

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.

[@rishigaikwad4488]

Note : At last condition checked, it should be checked |xz|

[@albinsopaj]

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.

[@raidboss8470]

thank you, the video is great

[@SpencerTwiddy]

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]

for proving something is not regular even one example is enough .

[@tomashorych394]

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

[@parasmittal3697]

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

@@parasmittal3697 No, for proving something irregular you still have to prove for a general case of a split.

[@minahany5894]

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

[@KyleDrewes]

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?

[@kainaatmakhani6550]

Informative lecture

[@shivangssinha1915]

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.

[@oguzhanakgun7673]

4:39 do we have to cover always 4 digits for y?

[@karin-yv3vb]

God bless you , I finally understood this fucking subject

[@palagirikeerthana1252]

Thank you so much sir....

[@rohitpatil8452]

sir can you please add again more videos for remaining topics like Turing machine and etc.

[@toxaim9936]

p =7 the message is clear Thala for a reason 😛

[@xoxoo4877]

Like the new instrumental for neso academy :D

[@KeyesAnthony]

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.

[@saivinay3292]

if u know the ans let me know

[@brijeshkanani4540]

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.

[@SathiyarajS-rh7kx]

Exam about next morning...now it's 12.44 am😂

[@valenntinabakia3591]

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

[@Soul_finder9]

how do you decide that above which we have to put the p as a power????

[@Soul_finder9]

please reply fast tommorrow is my exam

[@saikrishna-wk4gf]

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

[@gyatso_fam]

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.

[@kaywilfert8297]

@@gyatso_fam Thank you for clarifying. Helped me understand the problem!

[@tathagatamitra7376]

Thanks

[@sagnikbiswas3268]

So effectively if i is large enough, then the suffix will have two 1s but the prefix won’t

[@harishraja5567]

Exam in about 30 mins 👍👍👍

[@dhanushsivajaya1356]

Thankyou sir

[@arunsuresh8547]

How can i understand, the meaning of "yy" ? ..

[@mayankawasthi4802]

Why u take four value of Y in every question is it compulsory or we can take whatever we want?

[@achalakumari8346]

Thank you

[@sachinbhalla14]

please sir do more videos on this topic the topic is not clear within two examplle

[@muhammedajlan5628]

why there is any 2nd and 3rd cases like the previous vedio?

[@Welcomereddy]

how we are taking x,y,z values as x=oo and y=0000 and z=0100000001 ? please explain

[@shreyas_sridhar]

those are values which you can choose

[@ankitnayal6091]

Why you take value of S to be 0^p1 instead of taking 01^p

[@cavitsevinc3963]

aynen kanka ben de takıldım ona

[@DolaLado]

@@cavitsevinc3963 Öyle alsa dahi bir koşul yine de sağlanmayacaktı.

[@vidhipatel-bd2hq]

Sir. Why you always take a length of p=7 ?????

[@AhamedKabeer-wn1jb]

Thank you..

[@cavitsevinc3963]

Thank you sir

[@babitamangal9699]

very well done.. thanks... it is really awesome...

[@CSAkshay]

Why pumping length is 7 ? I have doubt

[@ahmedanassw]

thanks

[@sanjeethjavvaji5254]

Can we take pumping lemma P value any number ?

[@vaibhavgarg7345]

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

[@assylanbeknurmukhambet4154]

ibany indus, {0,1}* means 0^p 1^p, not 0^p 1

[@joey3070]

0^p 1 is a member of {0,1}*

[@chulbulji7417]

it is very helpful

[@ShaliniNegi24]

Thank you :D

[@suchithranv502]

Can I take the string as 1*0 1*0

[@miguelnuno928]

why 7 is the pumping number

[@ganeshpuranam7119]

doubt:why you took p on to the zero why not on to the 1.

[@arijitsaha1985]

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

[@VishalKhemnar360]

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

[@az100eletronics12]

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

[@VishalKhemnar360]

@@az100eletronics12 nope, all three conditions are to be satisfied...

[@abdulqadeer7907]

Closure is both on 0&1 then why u take only 0

[@ibrahimkhan3081]

WHY HE HAS USED ONLY 1 CASE TO PROOF IS IT OK TO PROVE WITH 1 CASE ONLY......

[@user3992]

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.

[@ron5101]

He explains at 6:52 , if you choose y that contains 1's you will not fulfill the second condition of the lemma

[@kunaljha2393]

@@ron5101 why so

[@rakshitnaidu5985]

@@kunaljha2393 If he uses the other condition i.e. ...010... as y, then it automatically fails the last test which is |xy|

[@calebmcnevin]

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

[@MrPerfectpunk]

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

[@ruchanarkhede4201]

Yes please can someone explain this

[@moshiurrahman2897]

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.

[@b.kowsalyagracy1865]

How to consider pumping length 7

[@mehrosenasir9974]

can anyone please tell me what does the * mean in the question?

[@shubhamsukum]

0 or more than 0

[@hirakhan8015]

If anybody knows which string will be accepted if its given like (0+1)*

[@cbalireddy9602]

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

[@kewsound]

Do we need to do 3 different cases to prove, like in the first video? Or is one case enough, like he did in this video? Maybe he explained it, but I missed it. Thanks in advance!

[@sinetenisinet]

The case depends on the language you are considering.

[@kewsound]

Thank you, that makes sense

[@asifferdous2432]

can i choose the value of P some other numbers except 7... what is the criteria for choosing P?

[@SaurabhKumar-vj2wi]

Yeah u can choose any value of p

[@VishalKhemnar360]

except 0

[@amrikdutta]

Can i divide xyz in any order??

[@chandankumarsingh9530]

how to choose the string i am not getting how to choose can anyone explain the meaning of (0,1)*

[@thorunitha7755]

If A={yy|y belongs to {a,b}} is regular or not?

[@javaexpertsa8947]

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.

[@vikrantpandey3522]

it is regular bro bcz you can draw a DFA for the following as A have only { a,b,aa,bb} as string.

[@jayanthsaikiran6624]

How to choose x y and z

[@divyavishwakarma2002]

If (01)* is represented by {0, 1}* in set theory. Then how would I represent (0 + 1)* in set theory

[@keigotakami1741]

Why cant we choose 0^p0^p? Someone please explain :(

[@wearenoless6732]

You can choose A=0^p 0^p Then , We will have one case y=0^k where |k| contradiction

[@asadmuhammad5859]

I don't think this is correct, the negation implies that we must prove that there exists a string S that does not obey the condition for all values of p.

[@tejaspanchmatiya]

why to use length of p=7 ?????

[@Peeveish]

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

[@axqd001]

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.

[@aslemos2009]

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.

[@michaelklaczynski3650]

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.

[@DoG-bz2tm]

Why you takes 7 as p

[@noorhassanwazir8133]

PL with respect to palindrome?

[@Sadhana_Pansare]

5 hrs left😢

[@ishitachatterjee4709]

Can we take 1^p here?and how the division of x ,y and z is done here?

[@johnnyzarizony868]

What would be the answer and prove to the question if language where there is 2 times as much 'a' as 'b' is regular or not? I did it like this but i'm not sure if i did it right. I chose my pumping length as P = 7 and proced like this: S = aaaaaaaaaaaaaabbbbbbb (14a 7b) i split it into xyz, in 3 ways: 1) aaaa aaaaaaaaaa bbbbbbb x y z I) for i = 2 i get: aaaa aaaaaaaaaaaaaaaaaaaa bbbbbbb 0

[@VishalKhemnar360]

if any one of the conditions is not met, the language is proven to be irregular... we choose x, y and z such that the 2nd and 3rd condition are always true, so we only have to show that the first condition in not satisfied and thus, the language cannot be regular as it doesn't satisfy all three conditions...

[@pawanthanay]

why 0^p only y cant we take 1^p ??

[@cavitsevinc3963]

You are exactly right babe

[@edulgl]

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.

[@fathimanavas483]

At 3:00 , how do we decide the string..?