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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.