Thanks to my supporters Yuri, vinetor, Ali (TH-cam) 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!
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
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 :)
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.
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
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.
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.
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?
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.
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
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.
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.)
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 :)
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.
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
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.
![ฮักเทื่อสุดท้าย - บอย ศิริชัย [OFFICIAL MV]](http://i.ytimg.com/vi/-1PoPoQ-B-k/mqdefault.jpg)
![[TH] VALORANT Champions Seoul - Grand Final - EDG vs TH](http://i.ytimg.com/vi/WvObMc9VelI/mqdefault.jpg)
![จบจนได้ ! | Black Myth: Wukong #007 [ตอนจบ?]](http://i.ytimg.com/vi/DSqvWndF0sw/mqdefault.jpg)
Thanks to my supporters Yuri, vinetor, Ali (TH-cam) 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 honestly wish my profs were as comprehensive as you. Thanks alot
Thanks very much Shourya
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'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!
Very beautiful and clear explanation, glad I found this channel !!!!!!!!!!!!!!!
Bro youre the best honestly. Thank you so much
This is probably the best explanation I've seen. Thank you!
yes jakub
Thanks!
Thumbnail op. I'm not gonna lie, you got u in the first half
This is like TH-cam 2008 or 2009 video lecture times and u know it is going to be so frickin good
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!
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're explaining so much better than my professor my man! Thank you for your videos! Wish I've discovered them earlier.
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.
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
*starts doing prime numbers
*Me Googles what are prime numbers
Phew that was a close one
For the Language L = {0^n.1^n | 0
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.
Thank you so much sir. Regards from the canary islands, Spain
wow now I get it, thank you so much!! you are helping so many people.
thank you so much, this was really helpful in understanding Pumping Lemma!
great vid, 30 times better than my crazy college professor.
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 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!
thank you for your help! i love your explanation
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.
Have a good day! Very helpful
thank you prof, you made my day!!!!!
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?
thank youuuuu!!!!!!!
Thank you for this video helped me alot!
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 👍.
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?
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?
thanks, you're the best
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)?
here is the best one
Thanks very much!
hey I get it now, thanks prof
wooow , you are the best thank you :)
Thanks :)
I have a question: why |Y|>=2? I don't understand.
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
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!
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.)
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 :)
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.
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
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.