Pumping Lemma for Regular Languages FOUR Examples and Proof Strategies!

Here we do four proofs of languages not being regular using the pumping lemma for regular languages, as well as give a proof strategy. The basic idea is to suppose that the language is indeed regular. Then the lemma asserts that a pumping constant "p" for that language exists. Then pick a string (chosen carefully) that is in the language and of length at least p. After observing all possible decompositions of that string into three pieces x, y, z (according to the rules), we choose a value of i such that xy^iz is not in the language. The video about the pumping lemma's proof is here:    • Pumping Lemma for Regular Languages F...  .

We do four different languages by showing slightly different variations on the theme of proof outlined above, shown in the chapters below:

0:00 - Introduction
1:30 - General Proof Strategy
7:05 - {0^n 1^n : n at least 0}
17:22 - {0^i 1^j : i strictly larger than j}
25:18 - {0^n : n is a perfect square}
34:18 - {0^n : n is a prime number}
44:56 - Conclusion

If you like this content, please consider subscribing to my channel:    / @easytheory  

▶SEND ME THEORY QUESTIONS◀
[email protected]

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