8
$\begingroup$

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!

$\endgroup$

migrated from stackoverflow.com Aug 7 '12 at 13:21

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

  • 1
    $\begingroup$ FYI - Regular expressions as defined in theoretical computer science and regular expressions that programmers use are related, but very different. $\endgroup$ – Cyborgx37 Aug 6 '12 at 23:32
  • 2
    $\begingroup$ 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. $\endgroup$ – Raphael Aug 8 '12 at 7:14
  • $\begingroup$ This is not correct, no. Your argument cannot depend on assuming $uv = a^{k^2}$. $\endgroup$ – Patrick87 Aug 18 '14 at 18:54
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Any hints on how to fix the proof? $\endgroup$ – Raphael Aug 8 '12 at 7:15
  • $\begingroup$ The OP "already know[s] the most simple solution", which I assume amounts to the fixed proof. $\endgroup$ – Yuval Filmus Aug 8 '12 at 12:41
  • $\begingroup$ @YuvalFilmus Not necessarily. There's a pretty straightforward proof using the Myhill-Nerode theorem which has nothing to do with the pumping lemma. That might be the one the OP is referring to. $\endgroup$ – Patrick87 Aug 18 '14 at 22:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy