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

  • @rsia08
    @rsia083 жыл бұрын

    5-minute concise explanations are so much better than lectures that are over an hour long. Much easier to remember :)

  • @rtasvadum1810
    @rtasvadum18103 жыл бұрын

    Again, this is higher quality than a majority of the classes I have taken so far. Thank you so much.

  • @aloafofbagels6381

    @aloafofbagels6381

    2 жыл бұрын

    That makes two of us.

  • @tw3039

    @tw3039

    2 жыл бұрын

    @@aloafofbagels6381 And three

  • @kennethaidoo361

    @kennethaidoo361

    2 жыл бұрын

    4 in mutual agreeance

  • @jaredcortes366

    @jaredcortes366

    Жыл бұрын

    5 in one accord

  • @stupidbro3983

    @stupidbro3983

    7 ай бұрын

    6 weary seekers of truth

  • @LL43216
    @LL432162 жыл бұрын

    Literally summed up like 2 hours of my lecture in 5 minutes thank you so much

  • @VahiMangai
    @VahiMangai3 жыл бұрын

    This is exactly what I needed before my teacher had us retake the test.

  • @csgo-gamer8765
    @csgo-gamer8765 Жыл бұрын

    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!

  • @simplystephanie595
    @simplystephanie595 Жыл бұрын

    Your videos explain content better than my whole semester of class. Thank you.

  • @sungwoooh4919
    @sungwoooh49193 жыл бұрын

    Thank you!! your voice is beautiful and easy to understand :)

  • @sahilahmed5228
    @sahilahmed5228 Жыл бұрын

    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.

  • @guywhodiedwithouthisdawg6260
    @guywhodiedwithouthisdawg6260 Жыл бұрын

    notice how non-regular language is so chill bout not being a regular language bro has a positive attitude

  • @guywhodiedwithouthisdawg6260

    @guywhodiedwithouthisdawg6260

    Жыл бұрын

    love your videos tho just subscribed

  • @BenBurgersJr
    @BenBurgersJr10 ай бұрын

    Thank you so much for this clear explanation and accompanying animation! Very clear and concise.

  • @soccerfan2969
    @soccerfan29693 жыл бұрын

    This saved me. Thank you so much. Sharing with the rest of my class right now.

  • @RagingAcid

    @RagingAcid

    2 жыл бұрын

    This guy doesn't understand how to get a cheeky curve

  • @heyjoeway

    @heyjoeway

    Жыл бұрын

    @@RagingAcid lmao that's fuckin evil

  • @top10top54
    @top10top543 жыл бұрын

    wonderful video ...waiting for context free languages

  • @l.w915
    @l.w9152 жыл бұрын

    very clear, love the pictures and the flow. thank you.

  • @HasanZobaer
    @HasanZobaer2 жыл бұрын

    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 :'(

  • @michaelshevelin2234
    @michaelshevelin22342 жыл бұрын

    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!

  • @slabbert
    @slabbert2 жыл бұрын

    Thanks so much! Truly helped more than any other sources I've encountered.

  • @harleykf1
    @harleykf13 жыл бұрын

    Thank you! Your videos are exceptional :)

  • @mr.froschi6526
    @mr.froschi6526 Жыл бұрын

    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.

  • @zodiackwolf
    @zodiackwolf2 жыл бұрын

    Fantastic video, thank you so much! Really made it much easier to understand proving non-regularity and my understanding of the pumping lemma too :)

  • @lumiere2598
    @lumiere25982 жыл бұрын

    I am really in love with your videos, please make more! (I'm spreading the words :D )

  • @oreoshake5951
    @oreoshake59513 жыл бұрын

    Thank you so much. This was very helpful and I was also confused in this part but now this is very clear.

  • @marsdelver8349
    @marsdelver83493 жыл бұрын

    These videos are so helpful, thank you!

  • @chehakmalhotra860
    @chehakmalhotra860 Жыл бұрын

    Beautiful playlist. Loved it

  • @afonsosantos1416
    @afonsosantos14163 ай бұрын

    You're litteraly saving me on Computing Theory

  • @marcos-vx3qj
    @marcos-vx3qj Жыл бұрын

    This video is excellent, it simply explains this confusing topic

  • @hassanjaber8169
    @hassanjaber81693 жыл бұрын

    DUDE YOU ARE A GODDESS, THANK YOU

  • @cheeesysandwich
    @cheeesysandwich Жыл бұрын

    Thank you so much; this was amazing! Just gave you your 1,000th like

  • @giggityyy...
    @giggityyy...2 жыл бұрын

    I have been on KZread since as log as I can remember,I can say this is TOP-NOTCH content 🔥.

  • @anastasiiabukhanova1877
    @anastasiiabukhanova18774 ай бұрын

    This is worth a lot! Thank you!

  • @tahamian4822
    @tahamian4822Ай бұрын

    I love your video! Please keep it up!

  • @Josh-tu9ji
    @Josh-tu9ji2 жыл бұрын

    These animations are soooo good. Please make a whole series on Automata! TYSM

  • @iskerop
    @iskerop3 жыл бұрын

    best explanation ive seen, thanks!

  • @madelynn_manis
    @madelynn_manis2 жыл бұрын

    This was super helpful thank you so much!

  • @Antonio9648
    @Antonio9648Ай бұрын

    Great explanation

  • @michelebissanti9055
    @michelebissanti90553 жыл бұрын

    you have saved my life! thanks

  • @samarthtandale9121
    @samarthtandale91214 ай бұрын

    Wow! This was a great proof indeed!

  • @aliramazani906
    @aliramazani906Ай бұрын

    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 🙏

  • @aliyyah82
    @aliyyah826 ай бұрын

    Wonderful video!

  • @sunviewer7
    @sunviewer72 жыл бұрын

    Super good explanation!!!!

  • @SzechSauce
    @SzechSauce2 жыл бұрын

    Brilliant! Thank you!

  • @nicholeconroy4558
    @nicholeconroy45582 жыл бұрын

    Can you please make a video about regular expressions and more on proofs please these have been very helpful

  • @suaie
    @suaie2 жыл бұрын

    Thank you. You are smarter than Neso Academy

  • @gbemisolaagboola8255
    @gbemisolaagboola82552 жыл бұрын

    well, i dont need a pumping lemma to proof you are not regular, amazing! for basic understanding ofcourse

  • @giovannilibrizzi
    @giovannilibrizzi6 ай бұрын

    this video may have just saved me for my midterm omg

  • @skyehelfant
    @skyehelfant Жыл бұрын

    Great video

  • @dhruv_jain99
    @dhruv_jain993 жыл бұрын

    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

    @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.

  • @fahidabdullah5637
    @fahidabdullah5637 Жыл бұрын

    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?

  • @jixster1566
    @jixster15662 жыл бұрын

    3:13 how are cases 2 and 3 possible if |xy|

  • @aster4405
    @aster440528 күн бұрын

    how to determine what length p to use?

  • @minhbeo0909
    @minhbeo09092 жыл бұрын

    Please increase the video audio quality next time. It's hard to hear through the speaker. Otherwise, the video is very helpful thank you!

  • @QuesterDesura
    @QuesterDesura2 жыл бұрын

    very well done :)

  • @astronautadomestico1343
    @astronautadomestico13432 жыл бұрын

    Ty so much

  • @shyngysbek6907
    @shyngysbek69076 күн бұрын

    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?

  • @gavinunrue2282
    @gavinunrue2282 Жыл бұрын

    amazing vid! The textbook or professor does not do this concept any justice lol

  • @JakisMaciek
    @JakisMaciek3 жыл бұрын

    Thanks! :>

  • @makenuo9041
    @makenuo90412 жыл бұрын

    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!

  • @adlai1
    @adlai12 жыл бұрын

    I hate that this video is 2 years old. Please make more videos!

  • @mangilalkaler3497
    @mangilalkaler34972 жыл бұрын

    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.

  • @lifetimeknight
    @lifetimeknight2 жыл бұрын

    better than automata course that i take in the college.

  • @crawbug8932
    @crawbug89322 жыл бұрын

    1:07 What about finite regular languages? They don't satisfy the pumping lemma but are still considered regular.

  • @kUmerZaidiSyed
    @kUmerZaidiSyed3 жыл бұрын

    10/10 video

  • @carpedm9846
    @carpedm98462 жыл бұрын

    Couldnt you have chosen a pair of 01, and thus keep the sequence? 010[10]1->010[10101010]1

  • @iliasvrynas9189

    @iliasvrynas9189

    2 жыл бұрын

    Yes but I think you need to find at least one sequence that is not part of the language

  • @cirosilvano6950

    @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.

  • @harshit1206
    @harshit12062 жыл бұрын

    Loved this!

  • @jasonzheng5839
    @jasonzheng58398 ай бұрын

    amazing. what am I paying my professor for

  • @drublacky1846
    @drublacky1846 Жыл бұрын

    😍

  • @blowingupcasinos
    @blowingupcasinos3 жыл бұрын

    This rules

  • @Shyzah
    @Shyzah2 жыл бұрын

    pushing p

  • @BehniaFB
    @BehniaFB3 жыл бұрын

    But the volume was too low...