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

Question

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!

Answer 1

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.