Proof that $a^{n^2}$ is not regular

Show that $L=\{a^{n^2} | n \geq 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| \geq m$ and there exists a decomposition $z = uvw, |uv| \leq m, |v| > 0$, so that $u(v^i)w$ is in the language for any $i \geq 0$.

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

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

Let $i = 2$. Then $u(v^2)w = a^{x+2y}$. But $\sqrt{x+2y}$ is not necessarily a natural number -> 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!

migrated from stackoverflow.comAug 7 '12 at 13:21

This question came from our site for professional and enthusiast programmers.

• FYI - Regular expressions as defined in theoretical computer science and regular expressions that programmers use are related, but very different. – Cyborgx37 Aug 6 '12 at 23:32
• You seem to have made some of the classic mistakes when applying the Pumping lemma. Please note our reference question for a detailed explanation and an example. – Raphael Aug 8 '12 at 7:14
• This is not correct, no. Your argument cannot depend on assuming $uv = a^{k^2}$. – Patrick87 Aug 18 '14 at 18:54

You can't deduce that $uv = a^{k^2}$, all that the pumping lemma gives you is that $|uv| \leq m$. Not all numbers less than $m$ are squares. Not only that, but even supposing that $uv = a^{k^2}$, there is no reason to assume that $v = a^{2k-1}$; all the pumping lemma gives you is that $v$ is non-empty. Finally, in order to get a contradiction, it is not enough that $x + 2y$ need not be a square, it must not be a square! Since $x$ and $x+y$ are adjacent squares, it is actually case that $x + 2y$ is not a square.