Nonregular languages: How to use the Pumping Lemma
We know that all regular languages must satisfy the pumping lemma. This means we can use the pumping lemma to prove that a language is NOT regular by showing that it does NOT satisfy the pumping lemma.
This video provides a little more intuition for how such a proof works.
If you aren't yet familiar with what exactly the pumping lemma is, check this video out first: • What is the Pumping Lemma
____________________
Additional resources:
Michael Sipser. 2006. Introduction to the Theory of Computation (2nd. ed.). International Thomson Publishing.
- The main source of my Theory of Computation knowledge (a textbook). Read Chapter 1.4: Nonregular Languages to learn more about the pumping lemma and examples of the formal proofs.
_____________________
And as always, this video project could not have been done without the support and guidance of Audrey St. John at Mount Holyoke College, a truly incredible professor-mentor-human.
Пікірлер: 84
5-minute concise explanations are so much better than lectures that are over an hour long. Much easier to remember :)
Again, this is higher quality than a majority of the classes I have taken so far. Thank you so much.
@aloafofbagels6381
2 жыл бұрын
That makes two of us.
@tw3039
2 жыл бұрын
@@aloafofbagels6381 And three
@kennethaidoo361
2 жыл бұрын
4 in mutual agreeance
@jaredcortes366
Жыл бұрын
5 in one accord
@stupidbro3983
7 ай бұрын
6 weary seekers of truth
Literally summed up like 2 hours of my lecture in 5 minutes thank you so much
This is exactly what I needed before my teacher had us retake the test.
This channel is criminally underrated! I cant emphasize how much this comic style awesome, adorable and clean is in its explanations. Thank you very much and keep up the good work!
Your videos explain content better than my whole semester of class. Thank you.
Thank you!! your voice is beautiful and easy to understand :)
when u take 3 cases, in those last 2 cases, you are taking y such that |xy| is already greater than p. You basically need to chose a y such that |y| is greater than 1 and less than p and |xy| must be less than p.
notice how non-regular language is so chill bout not being a regular language bro has a positive attitude
@guywhodiedwithouthisdawg6260
Жыл бұрын
love your videos tho just subscribed
Thank you so much for this clear explanation and accompanying animation! Very clear and concise.
This saved me. Thank you so much. Sharing with the rest of my class right now.
@RagingAcid
2 жыл бұрын
This guy doesn't understand how to get a cheeky curve
@heyjoeway
Жыл бұрын
@@RagingAcid lmao that's fuckin evil
wonderful video ...waiting for context free languages
very clear, love the pictures and the flow. thank you.
Yet another top quality video! From animation to explanation and the funny art style to the soothing voice its all just prefect! This channel is so underrated :'(
Lydia! You're the best! Thank you so much for your work! I would happy to see videos of yours about some problems like determining if the language is finite/ empty etc. Thanks again!
Thanks so much! Truly helped more than any other sources I've encountered.
Thank you! Your videos are exceptional :)
Thank you very much. I really liked the video. Honestly a kinda underaprecciated channel now that i look at the subs and views. You deserve more. Keep it up.
Fantastic video, thank you so much! Really made it much easier to understand proving non-regularity and my understanding of the pumping lemma too :)
I am really in love with your videos, please make more! (I'm spreading the words :D )
Thank you so much. This was very helpful and I was also confused in this part but now this is very clear.
These videos are so helpful, thank you!
Beautiful playlist. Loved it
You're litteraly saving me on Computing Theory
This video is excellent, it simply explains this confusing topic
DUDE YOU ARE A GODDESS, THANK YOU
Thank you so much; this was amazing! Just gave you your 1,000th like
I have been on KZread since as log as I can remember,I can say this is TOP-NOTCH content 🔥.
This is worth a lot! Thank you!
I love your video! Please keep it up!
These animations are soooo good. Please make a whole series on Automata! TYSM
best explanation ive seen, thanks!
This was super helpful thank you so much!
Great explanation
you have saved my life! thanks
Wow! This was a great proof indeed!
Hi Lydia, thanks for the amazing videos. I was wondering if you could also explain context free languages and how to use pumping lemma for them. Thanks 🙏
Wonderful video!
Super good explanation!!!!
Brilliant! Thank you!
Can you please make a video about regular expressions and more on proofs please these have been very helpful
Thank you. You are smarter than Neso Academy
well, i dont need a pumping lemma to proof you are not regular, amazing! for basic understanding ofcourse
this video may have just saved me for my midterm omg
Great video
In regular language we can make state diagram, so we know, number of states=p but in non-regular language we cannot make state diagram for language. then how we are going to find p for non-regular language?
@i3aluchi
2 жыл бұрын
To my humble knowledge, we don't necessarily choose P as the number of states as it is dependant on the language and not the machine.
Hi I had a question regarding the 3 cases for the pumping lemma. If we could prove one of the cases was true for the y value chosen, and it met all the three conditions for pumping lemma, then that would show the language is regular then, correct?
3:13 how are cases 2 and 3 possible if |xy|
how to determine what length p to use?
Please increase the video audio quality next time. It's hard to hear through the speaker. Otherwise, the video is very helpful thank you!
very well done :)
Ty so much
How do you define p? I know it is a pumping length but how you define it when you don't know which length is a pumping string?
amazing vid! The textbook or professor does not do this concept any justice lol
Thanks! :>
Sorry, I was so distracted by the beautiful sound of your voice - couldn't focus on what you were saying at first :-) But seriously, a great video, very intuitive and with nice metaphors like the "all-knowing Pumping Lemma" on its throne. Thanks for this!
I hate that this video is 2 years old. Please make more videos!
At 4:30, I assume you wanted to say : Assume the language is regular. Then given P, we find a string that can't, in fact, be pumped and still be in the language. This proves the language is non-regular, which contradicts our initial assumption.
better than automata course that i take in the college.
1:07 What about finite regular languages? They don't satisfy the pumping lemma but are still considered regular.
10/10 video
Couldnt you have chosen a pair of 01, and thus keep the sequence? 010[10]1->010[10101010]1
@iliasvrynas9189
2 жыл бұрын
Yes but I think you need to find at least one sequence that is not part of the language
@cirosilvano6950
Жыл бұрын
The language you’re talking about is different though. She was proving that the language consisting of an uninterrupted sequence of n 0s followed by an uninterrupted sequences of n 1s is irregular. Strings in such format correspond to stuff like 000111, 01, 00000001111111 and so on, while 01010101, for example, doesn’t belong to such language.
Loved this!
amazing. what am I paying my professor for
😍
This rules
pushing p
But the volume was too low...