Thanks to my supporters Yuri, vinetor, Ali (RUclips) and Bruno, Timmy, Micah (Patreon) for making this video possible! If you want to contribute, links are in the video description. Timestamps: 0:00 - Introduction 1:30 - General Proof Strategy 7:05 - {0^n 1^n : n at least 0} 17:22 - {0^i 1^j : i strictly larger than j} 25:18 - {0^n : n is a perfect square} 34:18 - {0^n : n is a prime number} 44:56 - Conclusion
I've looked in multiple books to get an intuition on pumping lemma proofs and kept scratching my head until I came upon this. by far the most clear. Thank you so much!
L={a^(n) | n is a prime number} x=a^(m-1),y=a^1,z=a^(p-m+1-1). s= a^(m-1) a^1 a^(p-m+1-1)>=p =>s=a^(1)a(p-m) >=p. by the lemma rules the string s must be in the language therefor s must be in length of any prime number and therefor p could potentionally be of the length of that prime number. the lowest prime number is 2 so we can start by i=2 a^(2)a(p-m) =>[reminder: m>=1 because x=a^(m-1) and |x|>=0 so if m>=0 it means that could be x=a^(0-1) meaning |x|>=-1 and thats not possible so m must start from 1 therfore m>=1]=> a^(2)a(p-1)=>a^(p+1). since p could be a prime number as mentioned in the start, it could be that p=2 and then a^(p+1)=>a^(2+1)=>a^(3)=> 'a' is in the length of a prime number so the resulted string of i=2 is still in the language and that was not helping us because we look for a contradiction. i=7 s=a^(7)a(p-1) => a^(p+6)=>a^(2+6)=>a^(8)=>'a' in the length of 8 and 8 is not a prime number so we reached a contradiction and therefor L is irregular language.
I never comment under youtube videos, but your lessons about Theory of Computation are pure gold and your explanation is always clear. Thank you kind sir
I had the following question on my homework: Let L = {w memberof {a,b}* | every prefix of w contains at least as many a's as b's} Example: Every Prefix of aba is {e, a, ab, aba}; aba is a member of L because in all prefix cases, the number of a's surpass the number of b's. Every Prefix of abbaa is {e, a, ab, abb, abba, abbaa}; abbaa is not a member of L because prefix abb has more b's than a's. I was having so much difficulty with this problem until I found your videos. The only legal strings would remain legal as we increment the i value, no matter how we break down the string. But when I watched your 17:22 example [ 0^i 1^j : i strictly larger than j ] I realized this is essentially the same problem I'm doing. I can't believe I didn't consider assigning i to be 0. Furthermore, my next homework problem was {a^k | k is prime} so this video ended up being a lifesaver! My professor doesn't teach with examples, or when she does, she uses examples that are so easy.
raising y to a power doesnt change the length of y itself, just like raising 10 to the power of 0 doesnt make 10 = 1, any string no matter how long it is picked 0 times is the null string
Thank you very much for this explanation! The way you break down XY and Z into what they COULD be while remaining generalized is immensely helpful in understanding this. Can we also use the closure properties of regular languages to, instead of contradicting the language itself, contradict the assertion that its complement is regular?
Yes. This is the same as saying that non-regular languages are closed under complement, which is true: suppose L not regular and L^c is regular. Closure under complement for regular langs says that (L^c)^c is regular. But this is L, a contradiction. So L^c must be not regular also.
Thank you for the detailed explanation! Timestamp: 10:48 I'm confused on what you said why x and y has only 0's when you can decompose the string where x = 0*, y = 01, z=1*. So how did your decomposition cover such case? Maybe I'm missing something in understanding.
First I thought you were too cute for Computation theory. I still think you are but your videos are the best!! Thank you prof for helping me throughout this course :)
You lost me on the last one at the end with the primes. If you replace (I * |Y|) with (1 + |Y|), then how can you assume I = |XZ| and still use it in the proof when the variable I has been swapped with (1 + |Y|) at that point?
hi! great video ! but question, for problem 2, you say it doesnt make a difference but if it was greater or equal, beta could've been 1 and then it would be regular... am l missing something? thank you so much
for o^i1^j couldnt i set j = p and i = p+ 1 and say |xyz| /leq p so then xyz one case is that they're entirely contained in 1s and if i pump that it's not in L
Technically, yes. Since L is regular, there must be a pumping length for it. (Can you see why L is regular? Note that the alphabet is {a, b}, and not something like {a, b, c}, where the answer is different.)
We actually have to test all possible decompositions. What I do in the video is have one "case" that covers all decompositions (at least the ones that obey the rules |xy| = 1). The reasoning is that if I forget to address one decomposition, then it's theoretically possible for a DFA to have a loop at the exact point where the "y" in the decomposition is.
The livestream on context-free languages in a few weeks certainly will hit it, and the video specifically on the PL for CFLs will appear on the channel...soon :)
And you have to go on ur way to pick just that i (the |xz|)? If i can be anything we want and it still should be in the language if the language is regular, couldn't we just pick any natural number (at least two) to point out that the length is not a prime? So confused right now that I cant sleep xD
Length of y, and because the "loop" that occurs in the DFA (which we called the "y" part) must involve at least one transition, which means at least one character read.
Bro take it easy. Don't shit post on the internet. It's fine to design catchy thumbnails to increase traffic and then providing valuable content at the end.
Thanks to my supporters Yuri, vinetor, Ali (RUclips) and Bruno, Timmy, Micah (Patreon) for making this video possible! If you want to contribute, links are in the video description.
Timestamps:
0:00 - Introduction
1:30 - General Proof Strategy
7:05 - {0^n 1^n : n at least 0}
17:22 - {0^i 1^j : i strictly larger than j}
25:18 - {0^n : n is a perfect square}
34:18 - {0^n : n is a prime number}
44:56 - Conclusion
The sad guitar into sums up my mood for the pumping lemma.
It is very sad, but I hope you're not sad!
I've looked in multiple books to get an intuition on pumping lemma proofs and kept scratching my head until I came upon this. by far the most clear. Thank you so much!
Lost me on the last one but i'd say this is the best explanation by far in the in the internet on the pumping lemma for R.L.
I honestly wish my profs were as comprehensive as you. Thanks alot
Thanks very much Shourya
Very beautiful and clear explanation, glad I found this channel !!!!!!!!!!!!!!!
This is probably the best explanation I've seen. Thank you!
yes jakub
Thanks!
This is like RUclips 2008 or 2009 video lecture times and u know it is going to be so frickin good
Bro youre the best honestly. Thank you so much
L={a^(n) | n is a prime number}
x=a^(m-1),y=a^1,z=a^(p-m+1-1). s= a^(m-1) a^1 a^(p-m+1-1)>=p =>s=a^(1)a(p-m) >=p. by the lemma rules the string s must be in the language therefor s must be in length of any prime number and therefor p could potentionally be of the length of that prime number. the lowest prime number is 2 so we can start by i=2 a^(2)a(p-m) =>[reminder: m>=1 because x=a^(m-1) and |x|>=0 so if m>=0 it means that could be x=a^(0-1) meaning |x|>=-1 and thats not possible so m must start from 1 therfore m>=1]=> a^(2)a(p-1)=>a^(p+1). since p could be a prime number as mentioned in the start, it could be that p=2 and then a^(p+1)=>a^(2+1)=>a^(3)=> 'a' is in the length of a prime number so the resulted string of i=2 is still in the language and that was not helping us because we look for a contradiction. i=7 s=a^(7)a(p-1) => a^(p+6)=>a^(2+6)=>a^(8)=>'a' in the length of 8 and 8 is not a prime number so we reached a contradiction and therefor L is irregular language.
For the Language L = {0^n.1^n | 0
I never comment under youtube videos, but your lessons about Theory of Computation are pure gold and your explanation is always clear.
Thank you kind sir
Thanks very much!
Thank you so much sir. Regards from the canary islands, Spain
I had the following question on my homework:
Let L = {w memberof {a,b}* | every prefix of w contains at least as many a's as b's}
Example: Every Prefix of aba is {e, a, ab, aba}; aba is a member of L because in all prefix cases, the number of a's surpass the number of b's. Every Prefix of abbaa is {e, a, ab, abb, abba, abbaa}; abbaa is not a member of L because prefix abb has more b's than a's.
I was having so much difficulty with this problem until I found your videos. The only legal strings would remain legal as we increment the i value, no matter how we break down the string.
But when I watched your 17:22 example [ 0^i 1^j : i strictly larger than j ] I realized this is essentially the same problem I'm doing. I can't believe I didn't consider assigning i to be 0.
Furthermore, my next homework problem was {a^k | k is prime} so this video ended up being a lifesaver! My professor doesn't teach with examples, or when she does, she uses examples that are so easy.
You're explaining so much better than my professor my man! Thank you for your videos! Wish I've discovered them earlier.
21:26 Wouldn’t i=0 effectively make |y| = 0, violating the condition length of y should be at least 1?
raising y to a power doesnt change the length of y itself, just like raising 10 to the power of 0 doesnt make 10 = 1, any string no matter how long it is picked 0 times is the null string
Thumbnail op. I'm not gonna lie, you got u in the first half
thank you so much, this was really helpful in understanding Pumping Lemma!
wow now I get it, thank you so much!! you are helping so many people.
Thank you very much for this explanation! The way you break down XY and Z into what they COULD be while remaining generalized is immensely helpful in understanding this. Can we also use the closure properties of regular languages to, instead of contradicting the language itself, contradict the assertion that its complement is regular?
Yes. This is the same as saying that non-regular languages are closed under complement, which is true: suppose L not regular and L^c is regular. Closure under complement for regular langs says that (L^c)^c is regular. But this is L, a contradiction. So L^c must be not regular also.
@@EasyTheory Wonderful! Thank you for the response! I just hope I got the right contradiction for the language, hahaha!
For the perfect square if you chose i = 3 it works as well [i think] as we would have p^2 < p^2 + 2
Yes i=3 works for that reason. Not sure if i=4 or more can be made to work, might be possible.
Thank you for the detailed explanation!
Timestamp: 10:48
I'm confused on what you said why x and y has only 0's when you can decompose the string where x = 0*, y = 01, z=1*. So how did your decomposition cover such case? Maybe I'm missing something in understanding.
Thanks - the main reason is that |xy|
@@EasyTheory I get it now. Again thanks a lot, really appreciate the video. Keep up the good job 👍.
Really simple and well thought out explanation. Please make a video on the CFG pumping lemma.
Video is coming out soon! Plus the livestream for CFLs will certainly cover this.
thank you for your help! i love your explanation
*starts doing prime numbers
*Me Googles what are prime numbers
Phew that was a close one
Hey Prof,
Can we also take 2p instead of p+1 as it is also at the border of the not being in language as |xy| p in the second example?
First I thought you were too cute for Computation theory. I still think you are but your videos are the best!! Thank you prof for helping me throughout this course :)
Thank you for this video. I still don't get it in the last example why we set r>=p+2 ( why we add 2)?
You lost me on the last one at the end with the primes. If you replace (I * |Y|) with (1 + |Y|), then how can you assume I = |XZ| and still use it in the proof when the variable I has been swapped with (1 + |Y|) at that point?
Have a good day! Very helpful
for the second example can we have i = 0 because |y| >= 1. I mean like if we have i=0 y does not exist so the condition is not true?
Thank you for this video helped me alot!
thank you prof, you made my day!!!!!
great vid, 30 times better than my crazy college professor.
hi! great video ! but question, for problem 2, you say it doesnt make a difference but if it was greater or equal, beta could've been 1 and then it would be regular... am l missing something? thank you so much
that's exactly what bugged me
for o^i1^j
couldnt i set j = p and i = p+ 1 and say |xyz| /leq p so then xyz one case is that they're entirely contained in 1s and if i pump that it's not in L
thank youuuuu!!!!!!!
I have a question: why |Y|>=2? I don't understand.
thanks, you're the best
here is the best one
Thanks very much!
is there a pumping lemma if L={w element of {a,b} | w contains an equal number of a's and b's}
Technically, yes. Since L is regular, there must be a pumping length for it. (Can you see why L is regular? Note that the alphabet is {a, b}, and not something like {a, b, c}, where the answer is different.)
hey I get it now, thanks prof
Super helpful video! Why do you only have to consider one possible decomposition?
We actually have to test all possible decompositions. What I do in the video is have one "case" that covers all decompositions (at least the ones that obey the rules |xy| = 1). The reasoning is that if I forget to address one decomposition, then it's theoretically possible for a DFA to have a loop at the exact point where the "y" in the decomposition is.
Gotcha, thanks! Excellent video, my professor went over this super quickly so this really helped.
@@ericmiller3673 You're welcome!
wooow , you are the best thank you :)
Any chance you'll tackle the pumping lemma for CFL? Please? XD
The livestream on context-free languages in a few weeks certainly will hit it, and the video specifically on the PL for CFLs will appear on the channel...soon :)
Thanks :)
wooosh.... That last ending went so high over... Why is there suddenly the (1 + |y|).. Not getting it even tho watched the part at least 10 times.. xD
And you have to go on ur way to pick just that i (the |xz|)? If i can be anything we want and it still should be in the language if the language is regular, couldn't we just pick any natural number (at least two) to point out that the length is not a prime? So confused right now that I cant sleep xD
29:25 why y is at least 1 ?
Length of y, and because the "loop" that occurs in the DFA (which we called the "y" part) must involve at least one transition, which means at least one character read.
@@EasyTheory Thanks, i really appreciate your help and effort.
Bro I like you a lot, but stop using women in thumbnails, this is Haram, they are not an object. It has nothing to do with Pumping Lemma.
Bro take it easy. Don't shit post on the internet. It's fine to design catchy thumbnails to increase traffic and then providing valuable content at the end.
chill bro not everyone is muslim if you dont want to look at do not.