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!
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!
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
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'
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.
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...
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....
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.
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.
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 ;)
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.
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?
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
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.
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
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.
Can't you use w = 0^n0^n and w = xyz as x = 0^\alpha, y = 0^\beta, z = 0^{p-\alpha-\beta}1^m0^p. xy^iz = 0 ^{p-\beta+i\beta}1^m0^n. |0^{p- \beta + i\beta}| = |0^p| p - \beta + \beta * i = p - \beta + \beta * i = 0 \beta * i = \beta only true for i = 1, if we take i = 2 , we can pump it out
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
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!
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 tutorial is just underrated! Hands down this is the best and most reliable tutorial I have seen concerning pumping lemma💯
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
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.
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.
This was so immensely helpful, following your step by step process leads me straight to the answer every time. Thank you so much!
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?
THIS is quality educational content. I wish there were more videos like this.
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
Your channel saved my class. Tysm
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.
This video changed my life. Thanks Mr. Easy Theory
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'
This video eased my pain. I can now see. Thanks a lot for producing such clear explanations!
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
After so much struggle for pumping lemma! I found the pumping lemma 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.
Best video on the Pumping Lemma subject. Awesome ❤
Thank you very much for your work!!! So clear and helpful!
Incredible explanation. Thank you so much for this video
Thank you, I really enjoy your videos and way of explaining.
Thanks from Portugal , very helpful indeed ❤
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?
I love your videos and passion. You make my life less anxious.
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...
Any way I can help you or the channel? Thank you for your the lessons.
I love you man i am dumb brain and even though ill forget this in a few weeks itll definitely help my exams
This was always difficult for me to understand thank you for going to extra lengths to explain this!
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.
Doing the lord's work!
you are literally so so good
Thank you for the lecture, cleared all my doubts!! 👐
what a great, easy to follow video! well done
Ser you are a theory god
Great explanation that was tooo helpful. Many thanks
32:02 Can't I choose i = 0, since that will still be valid?? Please reply!!
dude you are the goat
You are incredible!
Thank you so much for this, it helped me so much!
I'm so glad!
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....
Thank you very much.
You're such a good teacher 🙂
thank u so much for these kind of videos, super helpful!
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.
I usually dont comment
but thank you so fricking much for this
dude you're amazing
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.
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 ;)
You are amazing. Thank you
You are really good. Thank you so much.
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.
Thank you so much for this tutorial video!!!! Helps me so much in understanding this theory:)
You're a genius bro, thx a lot!!!! You've saved me :DDDD
2024 Oct 27
This is very helpful. Thank you!
I love you you really saved me 😭
For the factorial example the statement: p! + p < (p+1)! is not true when p = 1.
Does this matter?
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?
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)
this helps a lot thank you so much!!
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.
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. :(
really helpful, thanks
I love u dude.
For no.15, What is the kleene closure? What is defined by the predicate of the set?
You're a god
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 great video could you do one for : L= c^m a^n b^n OR a^n b^m ? Thanks
i feel ready for my toc paper
well done
at 1:52:00 can we have used 0^p#0^(P+P!)?
You earned one more subscriber
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
Now that's cool..........I took me a lot of afford to reach this video
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
Absolute gift to mankind 🤌😩
This is soooo goooood
goat
Hi professor could u please explain pumping lemma for a^4n for all n>=0
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
Thanks!!
wow, instant subscribe
Where did the p+(i-1)\beta come from in the non-palindromes proof (18)?
this
Awesome :)
How do you judge which string you should use for pumping
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.
please make a video about Myhill and Nerode.
Your wish is my command: ruclips.net/video/zmdkr4BMqR4/видео.html
@@EasyTheory Love you
Pumping lemma galore
Can you please do
{ 0^n 1^m 0^n | m,n ≥ 0} ???
Can't you use w = 0^n0^n and w = xyz as x = 0^\alpha, y = 0^\beta, z = 0^{p-\alpha-\beta}1^m0^p. xy^iz = 0 ^{p-\beta+i\beta}1^m0^n. |0^{p- \beta + i\beta}| = |0^p| p - \beta + \beta * i = p - \beta + \beta * i = 0 \beta * i = \beta only true for i = 1, if we take i = 2 , we can pump it out
at 31:11 where did that 2p after the equals come from?
This Would be nice to know
good vid
For Q3, if the word starts with 1. Will the z became 0^p?