Pumping lemma for CFG

Question

it is another my question. Can you give me hint to solve the following problem?

Prove that $L=\left\{a^{n^2}:n\ge 0\right\}$ is not a context-free language?

Thanks!

Answer 1

HINT: $L$ is not context-free, and you can use the pumping lemma to show this. Suppose that $L$ is regular, let $p$ be the pumping length, and let $w=a^{p^2}$. The pumping lemma says that we can decompose $w$ as $w=uvxyz$ in such a way that $|vxy|\le p$, $|vy|\ge 1$, and $uv^kxy^kz\in L$ for every $k\ge 0$. Obviously in this case each of the pieces $u,v,x,y$, and $z$ will just be a string of $a$’s. Let $m=|vy|\ge 1$.

• Show that $|uv^kxy^kz|=p^2-m+km=p^2+(k-1)m$ for each $k\ge 0$.

• Explain why it’s impossible that every term of the arithmetic progression $$\big\langle p^2+(k-1)m:k\ge 0\big\rangle$$ is a perfect square. (Extra hint: How far apart are $n^2$ and $(n+1)^2$?)