3
$\begingroup$

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!

  • 0
    A bit late, but i don't see why the claim $uv = a^{k^2}$ could be made. I think it should be rather stated, that |uv| \leq m \Rightarrow |v| \leq m \Rightarrow |uv^2w| \leq m^2 + m < (m+1)^22017-07-06

1 Answers 1

0

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.

  • 0
    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.2012-08-07