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!
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?
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.
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!
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.
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....
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 🙏
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😂)
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.
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
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
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.
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?
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.
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.
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
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
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'
Gaddamn I can't believe how easy this is. I've been struggling with this crap for days and I know it's not me, it's how pathetic the instruction of the material is. Sipser's book Theory of Computation is trash, he's trash as an instructor since he can't teach the material so that students can understand it. I finally understand looking at this video.
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 ;)
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...
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.
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?
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
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 😂.
This video eased my pain. I can now see. Thanks a lot for producing such clear explanations!
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?
This was always difficult for me to understand thank you for going to extra lengths to explain this!
You are incredible!
Your channel saved my class. Tysm
Ser you are a theory god
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.
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
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!
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
This tutorial is just underrated! Hands down this is the best and most reliable tutorial I have seen concerning pumping lemma💯
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.
THIS is quality educational content. I wish there were more videos like this.
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....
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 🙏
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?
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.
For no.15, What is the kleene closure? What is defined by the predicate of the set?
For the factorial example the statement: p! + p < (p+1)! is not true when p = 1.
Does this matter?
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
I love u dude.
This is soooo goooood
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)
I love you man i am dumb brain and even though ill forget this in a few weeks itll definitely help my exams
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.
Thank you, I really enjoy your videos and way of explaining.
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?
This was so immensely helpful, following your step by step process leads me straight to the answer every time. Thank you so much!
Can you please do
{ 0^n 1^m 0^n | m,n ≥ 0} ???
goat
Now that's cool..........I took me a lot of afford to reach this video
Any way I can help you or the channel? Thank you for your the lessons.
Thank you very much for your work!!! So clear and helpful!
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. :(
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.
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.
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
Thank you so much for this, it helped me so much!
I'm so glad!
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
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'
Gaddamn I can't believe how easy this is. I've been struggling with this crap for days and I know it's not me, it's how pathetic the instruction of the material is. Sipser's book Theory of Computation is trash, he's trash as an instructor since he can't teach the material so that students can understand it. I finally understand looking at this video.
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 ;)
i feel ready for my toc paper
Thank you very much.
Incredible explanation. Thank you so much for this video
Saw this video two days before my exam. And now i finally understand this topic. Thank you so much for this video.
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.
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...
Hey great video could you do one for : L= c^m a^n b^n OR a^n b^m ? Thanks
I usually dont comment
but thank you so fricking much for this
good vid
Thanks from Portugal , very helpful indeed ❤
This dude definitely calls Gifs as Jifs.
Great video though
After so much struggle for pumping lemma! I found the pumping lemma god 🖤
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.
You're a genius bro, thx a lot!!!! You've saved me :DDDD
Best video on the Pumping Lemma subject. Awesome ❤
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?
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
better than my prof could ever explain. TY
You're a god
boss
Awesome :)
Thank you
well done
How do you judge which string you should use for pumping
This video changed my life. Thanks Mr. Easy Theory
Great explanation that was tooo helpful. Many thanks
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
i love you
gg
what a great, easy to follow video! well done
For Q3, if the word starts with 1. Will the z became 0^p?
Hi professor could u please explain pumping lemma for a^4n for all n>=0
Thank you so much for this tutorial video!!!! Helps me so much in understanding this theory:)
Where did the p+(i-1)\beta come from in the non-palindromes proof (18)?
this
I love your videos and passion. You make my life less anxious.
Doing the lord's work!
You earned one more subscriber
thank u so much for these kind of videos, super helpful!
You are amazing. Thank you
Thank you for the lecture, cleared all my doubts!! 👐
You are really good. Thank you so much.
at 31:11 where did that 2p after the equals come from?
This Would be nice to know
I love you you really saved me 😭
you are literally so so good
wahch
really helpful, thanks
dude you're amazing
1:08:27 Litttttt
wow, instant subscribe
this helps a lot thank you so much!!
Pumping lemma galore
Thanks!!
WOWWW