Pumping Lemma for Regular Languages TWENTY Examples and Proof Strategies!
ฝัง
- เผยแพร่เมื่อ 1 ก.ค. 2024
- Here we do TWENTY examples of pumping lemma for regular language proofs. We do a whole lot of common language examples, as well as beginner all the way to advanced techniques. The timeline below will help you navigate to the proof of the language you are interested in.
Timeline:
0:00 - Intro
0:37 - 1. 0^n 1^n
12:09 - 2. Equal 0s and 1s
18:08 - 3. More 1s than 0s
26:40 - 4. 0^2n 1^n
32:23 - 5. 0^n 1 0^n
38:17 - 6. 0^n 1^m 0^(m+n), and 7. 0^n 1^m 0^(m*n)
47:40 - 8. 0^n 1^m : n != m
55:47 - 9. 0^n 1^m : n less than 3m
1:02:19 - 10. Perfect Squares
1:10:19 - 11. Powers of 2
1:17:18 - 12. Primes
1:26:14 - 13. 0^n 1^m : n/m is an integer
1:35:53 - 14. Strings with equal numbers of 00s and 11s
1:42:51 - 15. Strings of the form w # w, and 16. ww
1:51:57 - 17. w1 # ... # wn, wi and wj are all different
1:58:49 - 18. Non-Palindromes
2:05:05 - 19. xy such that |x|=|y|, x != y
2:13:22 - 20. Factorials
If you like this content, please consider subscribing to my channel: / @easytheory
▶SEND ME THEORY QUESTIONS◀
ryan.e.dougherty@icloud.com
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.
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 got a 93 for the exam and my pumping lemma proof is ALL right because of you! Thank you so much!!
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.
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 is quality educational content. I wish there were more videos like this.
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 🙏
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
This tutorial is just underrated! Hands down this is the best and most reliable tutorial I have seen concerning pumping lemma💯
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 video eased my pain. I can now see. Thanks a lot for producing such clear explanations!
Thank you, I really enjoy your videos and way of explaining.
Best video on the Pumping Lemma subject. Awesome ❤
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
Thank you very much for your work!!! So clear and helpful!
Incredible explanation. Thank you so much for this video
thank u so much for these kind of videos, super helpful!
what a great, easy to follow video! well done
Thank you for the lecture, cleared all my doubts!! 👐
You are incredible!
I love your videos and passion. You make my life less anxious.
This video changed my life. Thanks Mr. Easy Theory
This was always difficult for me to understand thank you for going to extra lengths to explain this!
Saw this video two days before my exam. And now i finally understand this topic. Thank you so much for this video.
Thanks from Portugal , very helpful indeed ❤
Thank you so much for this tutorial video!!!! Helps me so much in understanding this theory:)
Great explanation that was tooo helpful. Many thanks
Doing the lord's work!
Thank you very much.
Your channel saved my class. Tysm
you are literally so so good
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 helps a lot thank you so much!!
You are really good. Thank you so much.
dude you're amazing
You are amazing. Thank you
You're such a good teacher 🙂
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😂)
Did you understand why he didn't take 0^p0^p for the ww example at 1:44:00?
Thank you so much for this, it helped me so much!
I'm so glad!
I love you man i am dumb brain and even though ill forget this in a few weeks itll definitely help my exams
really helpful, thanks
better than my prof could ever explain. TY
You're a genius bro, thx a lot!!!! You've saved me :DDDD
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.
Awesome :)
This is soooo goooood
I love you you really saved me 😭
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...
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 ;)
well done
Thank you
Thanks!!
You earned one more subscriber
Ser you are a theory god
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 usually dont comment
but thank you so fricking much for 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.
wow, instant subscribe
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'
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?
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?
Hi professor could u please explain pumping lemma for a^4n for all n>=0
Hey great video could you do one for : L= c^m a^n b^n OR a^n b^m ? Thanks
good vid
goat
i feel ready for my toc paper
Where did the p+(i-1)\beta come from in the non-palindromes proof (18)?
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 no.15, What is the kleene closure? What is defined by the predicate of the set?
for 49:13 just take the complement and do the PL, you made it way more complex than it needs to be
Any way I can help you or the channel? Thank you for your the lessons.
For the factorial example the statement: p! + p < (p+1)! is not true when p = 1.
Does this matter?
How do you judge which string you should use for pumping
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.
WOWWW
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.
i love you
Pumping lemma galore
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)
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 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
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.
Now that's cool..........I took me a lot of afford to reach this video
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
Can you please do
{ 0^n 1^m 0^n | m,n ≥ 0} ???
wahch
at 31:11 where did that 2p after the equals come from?
This Would be nice to know
For Q3, if the word starts with 1. Will the z became 0^p?
please make a video about Myhill and Nerode.
Your wish is my command: th-cam.com/video/zmdkr4BMqR4/w-d-xo.html
@@EasyTheory Love you
1:08:27 Litttttt
This dude definitely calls Gifs as Jifs.
Great video though
gg
boss
20?! 💀😭
Rushed explanations
Absolute gift to mankind 🤌😩