Nonregular languages: How to use the Pumping Lemma
Вставка
- Опубліковано 24 лип 2024
- 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.
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.
That makes two of us.
@@aloafofbagels6381 And three
4 in mutual agreeance
5 in one accord
6 weary seekers of truth
Literally summed up like 2 hours of my lecture in 5 minutes thank you so much
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!
This is exactly what I needed before my teacher had us retake the test.
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!
Thank you so much for this clear explanation and accompanying animation! Very clear and concise.
Thank you!! your voice is beautiful and easy to understand :)
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.
Your videos explain content better than my whole semester of class. Thank you.
very clear, love the pictures and the flow. thank you.
Thanks so much!
Truly helped more than any other sources I've encountered.
Thank you! Your videos are exceptional :)
I am really in love with your videos, please make more! (I'm spreading the words :D )
Fantastic video, thank you so much! Really made it much easier to understand proving non-regularity and my understanding of the pumping lemma too :)
You're litteraly saving me on Computing Theory
DUDE YOU ARE A GODDESS, THANK YOU
Beautiful playlist. Loved it
This saved me. Thank you so much. Sharing with the rest of my class right now.
This guy doesn't understand how to get a cheeky curve
@@RagingAcid lmao that's fuckin evil
These videos are so helpful, thank you!
I have been on UA-cam since as log as I can remember,I can say this is TOP-NOTCH content 🔥.
I love your video! Please keep it up!
This is worth a lot! Thank you!
Thank you so much. This was very helpful and I was also confused in this part but now this is very clear.
Thank you so much; this was amazing! Just gave you your 1,000th like
This video is excellent, it simply explains this confusing topic
These animations are soooo good. Please make a whole series on Automata! TYSM
best explanation ive seen, thanks!
Wow! This was a great proof indeed!
wonderful video ...waiting for context free languages
Wonderful video!
This was super helpful thank you so much!
Great explanation
you have saved my life! thanks
notice how non-regular language is so chill bout not being a regular language bro has a positive attitude
love your videos tho just subscribed
Brilliant! Thank you!
Super good explanation!!!!
Great video
this video may have just saved me for my midterm omg
well, i dont need a pumping lemma to proof you are not regular, amazing! for basic understanding ofcourse
Thank you. You are smarter than Neso Academy
Can you please make a video about regular expressions and more on proofs please these have been very helpful
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 🙏
thank u very much
You definitely should open your own university. and then you should just sit there as a tutor and play these vids... you will be a tutor of the year for sure. :)
thanks for the great explanations. helped me a lot in my exams.
very well done :)
Thanks! :>
amazing vid! The textbook or professor does not do this concept any justice lol
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.
10/10 video
Ty so much
Thankssssss
3:13 how are cases 2 and 3 possible if |xy|
better than automata course that i take in the college.
Please increase the video audio quality next time. It's hard to hear through the speaker. Otherwise, the video is very helpful thank you!
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?
how to determine what length p to use?
I hate that this video is 2 years old. Please make more videos!
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?
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.
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?
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!
Loved this!
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.
1:07 What about finite regular languages? They don't satisfy the pumping lemma but are still considered regular.
😍
amazing. what am I paying my professor for
Couldnt you have chosen a pair of 01, and thus keep the sequence?
010[10]1->010[10101010]1
Yes but I think you need to find at least one sequence that is not part of the language
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.
This rules
pushing p
But the volume was too low...