MHB Show that the language is not context-free with the Pumping Lemma

[mathmari]

Hello!

Given the language $L$=$\{m^{(x)}: m$ is a symbol and $x$ is a perfect square$\}$, I have to show that L is not context-free using the Pumping Lemma.

First, we assume that L is context-free. So, from the pumping lemma there is a pumping length $p$. Let $s=m^{(p)}$, that can be divided into $uvxyz$.

How can I continue? How can I find something so that I can conclude that one of the conditions of Pumping Lemma is not satisfied?
Conditions of Pumping Lemma:
1) $ \forall i\geq 0$ $uv^ixy^iz$ $\epsilon$ $L$
2) $ |vy|>0$
3) $|vxy| \leq p$

 

[Evgeny.Makarov]

How can I continue? How can I find something so that I can conclude that one of the conditions of Pumping Lemma is not satisfied?
Conditions of Pumping Lemma:
1) $ \forall i\geq 0$ $uv^ixy^iz$ $\epsilon$ $L$
2) $ |vy|>0$
3) $|vxy| \leq p$

This fact requires the simplest version of the pumping lemma, where $|vxy| \leq p$ is not mentioned. The most important thing is that $uv^ixy^iz\in L$ and $|vy|>0$. That is, you can add $i|vy|$ to the length of $s$ for any $i\in\mathbb{N}$ and still stay in the language. Since $s\in L$, $p$ is a perfect square. Then so is $p+i|vy|$ for any $i$. You just need to show that such arithmetic progression cannot consists of perfect squares only. This fact can be proved using high school algebra.

 

[mathmari]

This fact requires the simplest version of the pumping lemma, where $|vxy| \leq p$ is not mentioned. The most important thing is that $uv^ixy^iz\in L$ and $|vy|>0$. That is, you can add $i|vy|$ to the length of $s$ for any $i\in\mathbb{N}$ and still stay in the language. Since $s\in L$, $p$ is a perfect square. Then so is $p+i|vy|$ for any $i$. You just need to show that such arithmetic progression cannot consists of perfect squares only. This fact can be proved using high school algebra.

I got it!
To show that $p+i|vy|$ is not a perfect square for any $i$, I have thought the following:
for $i=0$: p is a perfect square
for $i>0$: Since p is a perfect square, $p=w^2$. If $p+i|vy|$ is also a perfect square, then $w^2+i|vy|=n^2$ $\Rightarrow$ $i|vy|=n^2-w^2$ $\Rightarrow$ $i=\frac{n^2-w^2}{|vy|}$, but that is not always a number in $\mathbb{N}$. So, $p+i|vy|$ is not a perfect square for any $i$.

 

[Evgeny.Makarov]

To show that $p+i|vy|$ is not a perfect square for any $i$

Out of context, I would interpret this as saying that for all $i$, the number $p+i|vy|$ is not a perfect square (which does not have to be true). It's better to say, "$p+i|vy|$ is not a perfect square for some $i$" or "$p+i|vy|$ cannot a perfect square for all $i$".

I have thought the following:
for $i=0$: p is a perfect square
for $i>0$: Since p is a perfect square, $p=w^2$. If $p+i|vy|$ is also a perfect square, then $w^2+i|vy|=n^2$ $\Rightarrow$ $i|vy|=n^2-w^2$ $\Rightarrow$ $i=\frac{n^2-w^2}{|vy|}$, but that is not always a number in $\mathbb{N}$.

The last sentence is true, but it is not obvious at the level we are working here. (Of course if this were the remaining step to prove Fermat's last theorem, we could say that it is obvious.) I would recommend making this argument more detailed.

 

[mathmari]

Out of context, I would interpret this as saying that for all $i$, the number $p+i|vy|$ is not a perfect square (which does not have to be true). It's better to say, "$p+i|vy|$ is not a perfect square for some $i$" or "$p+i|vy|$ cannot a perfect square for all $i$".

The last sentence is true, but it is not obvious at the level we are working here. (Of course if this were the remaining step to prove Fermat's last theorem, we could say that it is obvious.) I would recommend making this argument more detailed.

How could I make it more detailed?

 

[Evgeny.Makarov]

Here is one way. Let $a,d$ be positive integers. It is sufficient to prove that an arithmetic progression $a+kd$, $k\in\mathbb{N}$, cannot consist exclusively of perfect squares. Take $k=d$ and suppose that $a+kd=a+d^2=n^2$ for some positive integer $n$. Then $n>d$, so $(n+1)^2-n^2=2n+1>2d+1>d$. That is, the next perfect square is greater than $a+(k+1)d$, which, therefore, cannot be a perfect square.

 

[mathmari]

Here is one way. Let $a,d$ be positive integers. It is sufficient to prove that an arithmetic progression $a+kd$, $k\in\mathbb{N}$, cannot consist exclusively of perfect squares. Take $k=d$ and suppose that $a+kd=a+d^2=n^2$ for some positive integer $n$. Then $n>d$, so $(n+1)^2-n^2=2n+1>2d+1>d$. That is, the next perfect square is greater than $a+(k+1)d$, which, therefore, cannot be a perfect square.

Thanks a lot!