# Using the pumping lemma to show that a language is not regular (Computer Science)

Show that $L=\{a^{n^2} | n \ge 0\}$ is not regular

Hey guys. I'm taking a CS class and this stuff is really new to me so bear with me. I tried to look if I get some contradiction by using the pumping lemma for regular languages and I worked it out like this:

Suppose $L$ is regular. Then there must be a natural number $m$ for all words $z$ in $L$ with length $|z| \ge m$ and there exists a decomposition $z = uvw$, $|uv| \le m$, $|v| > 0$, so that $uv^iw$ is in the language for any $i \ge 0$.

Consider the string $a^{m^2}$.

Then $uv = a^{k^2} = a^{x+y}$, for some $k \le m$ and $x = (k-1)^2$.
Then $v = a^y = a^{2k-1}$.

Let $i = 2$. Then $uv^2w$ = $a^{x+2y}$. But $\sqrt{x+2y}$ is not necessarily a natural number $\Rightarrow$ Contradiction! Hence, $L$ can not be regular.

Well, I know that this way is unnecessarily complicated and you can prove it differently (I already know the most simple solution). But my question here is: Is my proof valid as well or does it contain any flaw? Is it formally correct?

I appreciate any feedback! Thanks!

-
Are you sure you want to use the pumping lemma? I usually find that it is much easier and more straightforward to use the Myhill-Nerode theorem instead. Its name is not as fancy as "the pumping lemma", but the idea is extremely simple and direct. – Henning Makholm Aug 7 '12 at 0:08
Yeah, this would be a nice alternative. Nevertheless, I can expect assignments in my exam that require the use of the pumping-lemma and personally I want to get some experience with it as well. The assignments itself are rather basic, but as this mindset is quite new to me, I just need to get my fingers wet ;) – Tobias Hoffmann Aug 7 '12 at 0:43

Here are my comments. I leave some of the details to the reader.

Let's look at your proof starting from the beginning:

Suppose $L$ is regular. Then there must be a natural number $m$ for all words $z$ in $L$ with length $|z| \ge m$...

So far so good. You are following the logical structure of the Pumping Lemma. In order to continue this, I would change the rest of this paragraph as follows (changes italicized):

...such that $z$ can be decomposed as $z = uvw$ where $|uv| \le m$, $|v| > 0$, and $uv^iw$ is in the language for any $i \ge 0$.

Next:

Consider the string $a^{m^2}$.

This is perfect. You could state the obvious fact that this string is in $L$. Now you need decompose the string in such a way that there is a contradiction to the Pumping Lemma.

Then $uv = a^{k^2} = a^{x+y}$, for some $k \le m$ and $x = (k-1)^2$.

You are on the right track here. You are trying to decompose the chosen string. However, you are only decomposing it into $u$ and $v$, but haven't mentioned the remaining bits $w$. Even though this $w$ isn't used as part of the contradiction, you need to show it as part of the decompositions.

The other problem I see is that the word "Then" implies that you are deducing something. However, the exact decomposition is left to you as a choice rather than a logical deduction. With that in mind, I would continue with something like

Let $u = ...$, $v = ...$, and $w = ...$. Note that $a=uvw$.

I'll let you fill in the blanks in the above sentence. Next you consider some string of the form $uv^iw$ for some $i \ge 0$ and show that this string is no longer in $L$. I believe your ideas will fit into this framework.

-
Thank you very much, this helps a lot. I just wrote nothing about the fate of w, because with no further restrictions on w, I implied that w is in this case just empty for k=m or just the rest, whatever it is, if k<m. But I will include it now the next proofs, thanks a lot! – Tobias Hoffmann Aug 7 '12 at 0:52
Remember that your chosen string must have length at least $m$ and $|uv| \le m$. Therefore, $w$ is empty if and only if your chosen string has length $m$. In this case, your string has length $m^2$, so $w$ cannot be empty. Even if you chose a string and decomposed it so that $w$ is empty, you need to state this. – Code-Guru Aug 7 '12 at 13:10