Pumping Lemma for Regular Languages Example: Perfect Squares

Here we look at the language of perfect squares, and show that they are not regular. This is a classic proof using the pumping lemma, and relies on the fact that one can achieve a string that is not a perfect square, which would contradict the fact that the language was regular.

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

▶ADDITIONAL QUESTIONS◀
1. What if we set i = 3 in the proof?
2. Are there any other values of i that would also work?
3. What about any integer c for the language {0^{n^c} : n at least 0}?

▶SEND ME THEORY QUESTIONS◀
[email protected]

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