Pumping Lemma for Regular Languages TWENTY Examples and Proof Strategies!

[@EasyMoneyLuu]

My guy I would hope you know how many lives you've saved you are a true hero and we thank you

[@nxumalopromise4068]

Indeed a hero.

[@alanchang3577]

I got a 93 for the exam and my pumping lemma proof is ALL right because of you! Thank you so much!!

[@samuel_howell]

Sir. You are a godsend. Currently in a computational theory class. You've explained it 10 times better than my professor. And now I'm running through this ungodly amount of homework like a champ! Keep doing what you're doing bro!

[@enkhnyambattulga5123]

Started the comment with sir and endet it with a bro XD

[@aryanmn1569]

​@@enkhnyambattulga5123tone police detected

[@Heinzaroo]

holy MOLY I was so confused on how to split up xyz during my entire 1.5 hour class but you cleared that up for me within a matter of minutes. Thank you kindly

[@paswalt1502]

Exam in a month! I am honestly thankful to have stumbled upon your channel. Not only do I really enjoy the subject of computational theory, but also your videos. I really appreciate the use of colors, the clear and concise explanations and the obvious enjoyment of the topic at hand. Thanks, we need more people like you, really! There's a lot of other (even very big) topics in computer science not many people make videos about as dedicated as you. Keep up the work!

[@EasyTheory]

Thanks very much!

[@alinac5512]

Exam tomorrow and we're allowed to bring one sheet of handwritten paper. Guess whats gonna be on it 😂.

[@kristiyandimov1166]

THIS AWSOME DUDE saved my life at finals in software engineering course degree at university, keep up the good work and make more videos like these! Highly appreciated! Thank you!

[@resha7601]

This tutorial is just underrated! Hands down this is the best and most reliable tutorial I have seen concerning pumping lemma💯

[@sukulhanda]

Your channel saved my class. Tysm

[@SleepyLellek]

My man, you are the GOAT! Thank you so much for showing these proofs. I finally managed to understand the application of the Pumping Lemma, thanks to your explanations 🙏

[@soumyadeeproy6611]

Simply blown away by your style of teaching, really fabulous explanation... Now I will watch every single video made by you on theory of computation

[@juliusfranzen9704]

Saw this video two days before my exam. And now i finally understand this topic. Thank you so much for this video.

[@cmptlylost]

This was so immensely helpful, following your step by step process leads me straight to the answer every time. Thank you so much!

[@mariajosepav]

You helped me nail my exam! Thank you so much for the free educational content you create, your videos have become a must for me to follow as I go through my course (even more important than the course itself most times😂)

[@KurokishiYT]

Did you understand why he didn't take 0^p0^p for the ww example at 1:44:00?

[@tongpoo8985]

THIS is quality educational content. I wish there were more videos like this.

[@Rockyzach88]

Watched up to 12 minutes just now. It makes perfect sense. I don't understand why more instructors of this concept don't break down the exponents this much. Instead they sort of just describe it in english and it gets kind of confusing.

[@ericshapiro4932]

Thank you for these very-well explained proof examples. I now understand how to properly select i's given varying pumping lemma proofs. You are a godsend

[@mnmLCoder]

better than my prof could ever explain. TY

[@erenasker825]

This video changed my life. Thanks Mr. Easy Theory

[@artianrika8329]

Thank you prof. You covered everything we need

[@FreeDomSy-nk9ue]

I was actually just starting to look for pumping lemma proofs, then this showed up!

[@EasyTheory]

Lucky timing ;) hope it helps!

[@FreeDomSy-nk9ue]

@@EasyTheory The exam is in 3 days. Thank you

[@what8212]

google is always listening

[@rodrigoresende8328]

This video eased my pain. I can now see. Thanks a lot for producing such clear explanations!

[@bigsanity]

Best video on the Pumping Lemma subject. Awesome ❤

[@lakshaysingla7412]

After so much struggle for pumping lemma! I found the pumping lemma god 🖤

[@tomassantos5008]

Thanks from Portugal , very helpful indeed ❤

[@j.j.3759]

Thank you :) I'm taking a theoretical informatics class and I like the professor, but his way of explaining things is sometimes hard to follow. This makes everything so much clearer.

[@prevoid398]

you are absouletly genius bro

[@simox7492]

Thanks man you saved me, this is gold

[@erichgruttner]

Thank you very much for your work!!! So clear and helpful!

[@al-mouhannadhafez3817]

Thank you for useful explaining. Please note that in the last example we have P! + P < (P+1)! iff : P>=2 so we have to choose p' = max (P,2) and deal with p'

[@Karim-nq1be]

Thank you, I really enjoy your videos and way of explaining.

[@toddblackmon]

In the final factorial proof, I think there is a slight error for the case where p = 1 (which is allowed by the lemma). In that case, the final inequality p!+p < (p+1)! does not hold since 1!+1 = 2!. I think the solution to this issue is shown in the previous where you just used a longer w string. Something like w = 0^(p+1)! could be used instead.

[@abnerandreymartinezzamudio3366]

I love your videos and passion. You make my life less anxious.

[@miguelmendez3236]

This was always difficult for me to understand thank you for going to extra lengths to explain this!

[@sanskaripatrick7191]

Incredible explanation. Thank you so much for this video

[@ayushsharma397]

Really helpful! This kind of clear explanation shows how deep and clear your understanding is in this subject. Commendable! Thankyou so much! are you a scientist by any chance?

[@MultiDragola]

I love you man i am dumb brain and even though ill forget this in a few weeks itll definitely help my exams

[@NoClipShort]

what a great, easy to follow video! well done

[@premnath2333]

32:02 Can't I choose i = 0, since that will still be valid?? Please reply!!

[@greendroid10]

Exam tomorrow and finally understand how to do these kinds of problems at all! Wish I had seen this video before I turned in my last assignment though...

[@adetunjiadewoye2534]

Doing the lord's work!

[@thinkverse2672]

Thank you for the lecture, cleared all my doubts!! 👐

[@김지은-p1b7y]

49:36 i tried my best, but i cant't understand why i can't pump down and prove that. when i did pumping down, i get b (number of y) = 1 and i = 0. Is it problem that only we can prove it only when b=1 whereas other prove before it was okay in all b?? I thought i got everything right before it but now i'm really confused....

[@duncanjr.5905]

you are literally so so good

[@sabrinchahed9312]

Great explanation that was tooo helpful. Many thanks

[@rildofranco2863]

Any way I can help you or the channel? Thank you for your the lessons.

[@Altair02901]

thank u so much for these kind of videos, super helpful!

[@vimalathithand917]

You are a god....! I'm soo greatfull and this was an awesome video! Though i need to think on choosing the w in some cases which i am sure that i will figure it out ;)

[@NaveenRodriguez]

dude you are the goat

[@alicets9682]

You are incredible!

[@Tlaloc2325]

Thank you so much for this, it helped me so much!

[@EasyTheory]

I'm so glad!

[@iTux82]

wow. it makes a lot more sense this way. I dont know why my prof and and textbook didnt bring up the exponent algebra required.

[@silvo9460]

at 1:52:00 can we have used 0^p#0^(P+P!)?

[@mahdi-hasan]

Can you please show how to solve no 9, if n > 3m?

[@LENOKOK]

You're such a good teacher 🙂

[@AP-gu8wv]

Thank you so much for this tutorial video!!!! Helps me so much in understanding this theory:)

[@riskoveryclips]

dude you're amazing

[@valuetraveler2026]

Ser you are a theory god

[@pietrociarmatori4506]

Question: In 2:05:11 you used the p! trick to prove that x and y can be different. Could you have used a string of this format: 0^p11^p0 (x terminates after the first 1) to prove that x an y can be of different length? I ask this because I understand that to prove that a string is not anymore in the language, in this case, proving that one of the two conditions fails is enough.

[@andrespolop]

You're a genius bro, thx a lot!!!! You've saved me :DDDD

[@aaaaaaaa-xg4je]

I usually dont comment but thank you so fricking much for this

[@iefeatas]

Great job

[@ahmetresatdemir3216]

Sir, for the primes question, does this approach works: similar to your choosing r, choose r such that r>p. after some calculation we will find 0^(r+(i-1)B). pumpu up i-1=r so, 0^(r+(i-1)B)=0^(r+rk)=0^(r(1+B)). Since B>0, there are two multiplier, which shows it is not prime.

[@dlarald]

I love you you really saved me 😭

[@andreassadi5064]

You are amazing. Thank you

[@haydengalloway5177]

You are really good. Thank you so much.

[@Ata-r5r]

At 2:19:46, why did we say it is strictly less than p!(p+1), if p would be 1, the expressions are equal?

[@undercover4874]

May be we could just say for p>=2 at the start then continue the proof

[@Sergeak21]

for the problem1 at 47:44 L = {0^n 1^m : m != n} you said that w = 0^p+1 1^p won't work and i agree, but what about w = 0^p 1^p+1? it seems that u should be able to pump in 0's to get to the number of 0's the same as the number of 1's? is there a reason for why this won't work? P.S love ur vids

[@karidse]

i just tried and it is not possible bcz you cannot prove in any way that p+B(i-1) = p+1 .

[@bananabr3d]

@@karidse Shouldnt it be p+B(i-1)

[@charlesmerritt8127]

For no.15, What is the kleene closure? What is defined by the predicate of the set?

[@egemenatik2983]

For the eighth example, would it be correct if we apply the following solution?: If we take intersection of the language (0*1*) with the complement of the language in the example, we get 0^n1^n. If the language in the question is a regular language, then its complement must also be a regular language by closure property of regular languages under complement operation. Again, if we take intersection of this resulting language with (0*1*), which is also a regular language because we can write regex of it, then we should have a regular language as result. However, we get 0^n1^n: n>=0. We already proved that this is not a regular language, so by contradiction we can say that the language in the example is not a regular language.

[@youssefbrahim500]

this helps a lot thank you so much!!

[@idslw3489]

47:20 misleading moment - L3 could never be 0*1*. It is 0^n1^m which is not equivalent to 0* 1*

[@yasamankhoobyari4690]

Thank you very much.

[@prerakpanwar9853]

Professor for 3rd question where the number of 1's > the number of 0's. Could you please tell me a String that will work both in pump up and pump down? Your prompt response is highly appreciated. Thank you.

[@bobbobby3123]

For the factorial example the statement: p! + p < (p+1)! is not true when p = 1. Does this matter?

[@srajangupta4468]

really helpful, thanks

[@yousafkhalid5263]

How do you judge which string you should use for pumping

[@studywithnya]

I love u dude.

[@char117]

Very helpful thank you. However I'm a bit stuck as to why in question 11 for the statement 2^(p) + (i-1)beta is a power of 2. Is it because in this specific question the language is 0^2^n? as in u just take the 2 because its multiplying by 2?

[@gamegladiators777]

You earned one more subscriber

[@fpsgod7259]

Hey great video could you do one for : L= c^m a^n b^n OR a^n b^m ? Thanks

[@bloodthirstybutcher8365]

at 31:11 where did that 2p after the equals come from?

[@janfiske1934]

This Would be nice to know

[@sobkhed1716]

well done

[@supamdeepbains5172]

This is soooo goooood

[@TheTortinator]

You're a god

[@juhasauna-aho7811]

LEGEND

[@TDYT103]

2024 Oct 27 This is very helpful. Thank you!

[@rookiecookie8258]

Hey, really like your videos! Can one use 0^r for primes where r is the first prime after p and then choose i to be (r−1)! + 2 and apply Wilson's theorem?

[@therealestvideos-sf]

for 49:13 just take the complement and do the PL, you made it way more complex than it needs to be

[@iluvgranola2313]

hey, can you explain please ? I thought I got it until this example. I literally want to give up. :(

[@sumabanoth4314]

Hi professor could u please explain pumping lemma for a^4n for all n>=0

[@duncanjr.5905]

i feel ready for my toc paper

[@Ivan-ou5nq]

Thank you

[@nataliasalesaragao4410]

Thanks!!

[@aayushbhandari4387]

wow, instant subscribe

[@jewelleharper6285]

Your sweatshirts should be black with multi colors, because it's kind of your signature (also, because I can't actually keep anything white)... Then I would buy one. But seriously awesome videos as always

[@lookwhoneedsahobbie]

Where did the p+(i-1)\beta come from in the non-palindromes proof (18)?

[@zacharylilley3361]

this

[@NuggzBii]

I don't think the string chosen in problem 19 is actually in the language, and if it is, it's not easy to tell. Can someone please describe how 0^p10^p! +p1 are even in length. If string x is 0^p1, and string y is 0^p!+p1, they are not in the language. Even if x is 0^p and y is 0^p!+p, it's not in the language

[@reese322]

First of all, thank you for your videos, they're helping a lot passing my exam. You explanations are very clear and intuitive. At 48:00, can't you just prove that by showing that the complement (0^p1^p) is not regular?

[@EasyTheory]

Close! You can do that but then have to intersect the original language with 0*1* to get to {0^p 1^p : p >= 0}, since it's not exactly the complement. What I did here is a "direct" proof that does not assume any other facts about regular languages.

[@augustopinheiro]

Awesome :)

[@clashking8427]

Now that's cool..........I took me a lot of afford to reach this video