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!
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!
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
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!
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 🙏
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.
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😂)
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
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.
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'
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?
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...
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.
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 ;)
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.
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....
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
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?
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.
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.
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.
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.
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?
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
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?
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
My guy I would hope you know how many lives you've saved you are a true hero and we thank you
Indeed a hero.
I got a 93 for the exam and my pumping lemma proof is ALL right because of you! Thank you so much!!
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!
Started the comment with sir and endet it with a bro XD
@@enkhnyambattulga5123lol
@@enkhnyambattulga5123tone police detected
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!
Thanks very much!
Exam tomorrow and we're allowed to bring one sheet of handwritten paper. Guess whats gonna be on it 😂.
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
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!
Your channel saved my class. Tysm
This tutorial is just underrated! Hands down this is the best and most reliable tutorial I have seen concerning pumping lemma💯
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 🙏
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
Saw this video two days before my exam. And now i finally understand this topic. Thank you so much for this video.
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.
THIS is quality educational content. I wish there were more videos like this.
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😂)
Did you understand why he didn't take 0^p0^p for the ww example at 1:44:00?
better than my prof could ever explain. TY
This was so immensely helpful, following your step by step process leads me straight to the answer every time. Thank you so much!
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
you are absouletly genius bro
This video changed my life. Thanks Mr. Easy Theory
Thank you prof. You covered everything we need
I was actually just starting to look for pumping lemma proofs, then this showed up!
Lucky timing ;) hope it helps!
@@EasyTheory The exam is in 3 days. Thank you
google is always listening
This video eased my pain. I can now see. Thanks a lot for producing such clear explanations!
Thanks man you saved me, this is gold
After so much struggle for pumping lemma! I found the pumping lemma god 🖤
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.
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'
Best video on the Pumping Lemma subject. Awesome ❤
I love your videos and passion. You make my life less anxious.
Thank you very much for your work!!! So clear and helpful!
Doing the lord's work!
Thanks from Portugal , very helpful indeed ❤
Incredible explanation. Thank you so much for this video
This was always difficult for me to understand thank you for going to extra lengths to explain this!
I love you man i am dumb brain and even though ill forget this in a few weeks itll definitely help my exams
Thank you, I really enjoy your videos and way of explaining.
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?
you are literally so so good
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...
what a great, easy to follow video! well done
Thank you so much for this, it helped me so much!
I'm so glad!
I usually dont comment
but thank you so fricking much for this
Great explanation that was tooo helpful. Many thanks
Ser you are a theory god
Thank you for the lecture, cleared all my doubts!! 👐
You're a genius bro, thx a lot!!!! You've saved me :DDDD
dude you are the goat
You are incredible!
thank u so much for these kind of videos, super helpful!
dude you're amazing
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.
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.
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 ;)
Thank you so much for this tutorial video!!!! Helps me so much in understanding this theory:)
You're such a good teacher 🙂
32:02 Can't I choose i = 0, since that will still be valid?? Please reply!!
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.
I love you you really saved me 😭
You are really good. Thank you so much.
Any way I can help you or the channel? Thank you for your the lessons.
You are amazing. Thank you
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....
this helps a lot thank you so much!!
Great job
really helpful, thanks
at 1:52:00 can we have used 0^p#0^(P+P!)?
47:20 misleading moment - L3 could never be 0*1*. It is 0^n1^m which is not equivalent to 0* 1*
Can you please show how to solve no 9, if n > 3m?
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
i just tried and it is not possible bcz you cannot prove in any way that p+B(i-1) = p+1 .
@@karidse Shouldnt it be p+B(i-1)
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?
May be we could just say for p>=2 at the start then continue the proof
You earned one more subscriber
for 49:13 just take the complement and do the PL, you made it way more complex than it needs to be
hey, can you explain please ? I thought I got it until this example. I literally want to give up. :(
Thank you very much.
2024 Oct 27
This is very helpful. Thank you!
This is soooo goooood
I love u dude.
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?
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.
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.
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.
For no.15, What is the kleene closure? What is defined by the predicate of the set?
i feel ready for my toc paper
For the factorial example the statement: p! + p < (p+1)! is not true when p = 1.
Does this matter?
wow, instant subscribe
Now that's cool..........I took me a lot of afford to reach this video
You're a god
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.
well done
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?
Hey great video could you do one for : L= c^m a^n b^n OR a^n b^m ? Thanks
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
at 31:11 where did that 2p after the equals come from?
This Would be nice to know
LEGEND
Thank you
Thanks!!
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?
Hi professor could u please explain pumping lemma for a^4n for all n>=0
How do you judge which string you should use for pumping
Where did the p+(i-1)\beta come from in the non-palindromes proof (18)?
this
Awesome :)
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