Master the Pumping Lemma: 4 Examples & Strategies to Prove Languages Are Not Regular 🚀

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: https://www.youtube.com/watch?v=A5FiVgd0QyQ.

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

Easy Theory Website: https://www.easytheory.org
GoFundMe: https://www.gofundme.com/f/easy-theory-video-studio
Patreon: https://www.patreon.com/EasyTheoryYT
Fourthwall: https://easy-theory-llc-shop.fourthwall.com
Problem Solving channel: ​⁠ @easytheoryprobsolve

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: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1