Pumping Lemma for Regular Languages PROOF IN 4 MINUTES - Easy Theory

Here we give a very quick proof of the pumping lemma for regular languages. The question just asks about strings that are also accepted in a given DFA. We partition the string up into pieces (as long as the string was accepted and at least the number of states), and repeat the middle piece, yielding another accepted string. Then, we make observations about where the middle piece can be.

▶ADDITIONAL QUESTIONS◀
1. Is any one of the three conditions unnecessary?
2. Does the initial string have to be accepted?
3. Does the initial string have to be at least the number of states in length?

▶SEND ME THEORY QUESTIONS◀

▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught over 12 courses at Arizona State University, as well as Colgate University, including several sections of undergraduate theory.

[taaaaaaay]

Not gonna lie, hardest part of my CS degree so far.

[mattinielsen]

I thought it was pretty good, thank you. Something i noticed was that in the last seconds where you finish the proof we can't really tell what is going on because of those pop-ups.

[zkierkniekjion]

I've been trying to solve pumping lemma problems without understanding this and it felt so alien to me. This explanation clears it all up for me, but I'll have to watch it a few more times XD

[Edbull]

thank you for this video, it really made my day. I was able to better understand something I was struggling with.

[dorsaghasri]

It was really helpful, thanks a lot 🙏🏻

[mattinielsen]

Do you know what kind of proof this is? is it by construction or what you would call a direct proof?

[chinmayjose]

Pumping lemma assumes that in the xyz we find, y is the looping part. Here is where i find the problem. Ofcourse if you can construct a dfa it is regular. If you could, you wouldn't be trying pumping lemma in first place.Without a dfa we are blind in knowing whether we chose y properly. If we choose a y where there is no loop then it may not mean language is not regular even if we prove so using the pumping lemma. How to get around this ? Pumping lemma must be more explicit about this.

[hectorg]

Cram tip: Watch this in 2x the speed to see it in 2 minutes.