# 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!

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