Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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
add comment

1 Answer 1

up vote 0 down vote accepted

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.