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