Pumping Lemma for Regular Languages TWENTY Examples and Proof Strategies!

Here we do TWENTY examples of pumping lemma for regular language proofs. We do a whole lot of common language examples, as well as beginner all the way to advanced techniques. The timeline below will help you navigate to the proof of the language you are interested in.

Timeline:
0:00 - Intro
0:37 - 1. 0^n 1^n
12:09 - 2. Equal 0s and 1s
18:08 - 3. More 1s than 0s
26:40 - 4. 0^2n 1^n
32:23 - 5. 0^n 1 0^n
38:17 - 6. 0^n 1^m 0^(m+n), and 7. 0^n 1^m 0^(m*n)
47:40 - 8. 0^n 1^m : n != m
55:47 - 9. 0^n 1^m : n less than 3m
1:02:19 - 10. Perfect Squares
1:10:19 - 11. Powers of 2
1:17:18 - 12. Primes
1:26:14 - 13. 0^n 1^m : n/m is an integer
1:35:53 - 14. Strings with equal numbers of 00s and 11s
1:42:51 - 15. Strings of the form w # w, and 16. ww
1:51:57 - 17. w1 # ... # wn, wi and wj are all different
1:58:49 - 18. Non-Palindromes
2:05:05 - 19. xy such that |x|=|y|, x != y
2:13:22 - 20. Factorials

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.