1
$\begingroup$

I am attempting to prove via the pumping lemma that $1^{n^2}$ is not a regular language. I started with

$w = 1^{p^2}$

I then divided $w$ into $xyz$, where:

$x = 1^{l}$

$y = 1^{m}$

$z = 1^{{p^2}-l-m}$, where $l+m \le p$ and $m \ge 0$.

Now, when I choose $i=2$ in order to get $xy^2z$, I end up with:

$1^{{p^2}+m}$, since $0 > m \le p $, the sum $m+p^2$ could certainly not be a square because the difference between $p^2$ and the next square is always greater than $p$ for all natural numbers.

Q.E.D

However, even if the basic logic of the proof is right, it does not seem as if my conclusion is as strong as it should be. Is there a more formal, proof-like manner to reach my conclusion with the same $s$ and $xyz$?

$\endgroup$
  • 1
    $\begingroup$ I don't see anything un-proof-like in what you've done. Proofs are human-to-human communication, the emphasis is on clarity in the exposition of the proof steps rather than adherence to some arbitrary standard of formality. $\endgroup$ – quicksort Feb 9 '17 at 18:10
  • $\begingroup$ @quicksort would it be worthwhile to modify my conclusion to say that m must be less than 2p+1, for the next square, so therefore there is a contradiction? $\endgroup$ – tpm900 Feb 9 '17 at 18:18
1
$\begingroup$

Your proof is correct, but you could elaborate your arguments if you wish.

We have $m\gt 0$ (typo in your question I think, you have used $\ge$) and $l+m\le p$. As $l\ge0$, $0\le p-m\implies m\le p$

$$m\gt0\implies p^2+m\gt p$$ $$\begin{align}m\le p&\implies p^2+m\le p^2+p\lt p^2+2p+1=(p+1)^2\\ &\implies p^2+m\lt (p+1)^2\end{align}$$

$p\lt 2p+1$ is true because $p\ge1$.

Thus, $p^2+m$ lies strictly between two consecutive squares, and hence cannot be a perfect square.

$\endgroup$

Your Answer

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

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