# How to prove {a^(n^2) | n>0} is not context-free?

So I have a language: $$L = \{a^{n^2} \mid n > 0\}$$ I need to prove that this language isn't context-free using the pumping lemma. I have a vague thought process as to how to do the proof but I'm sort of doubting its validity.

So I take a pumping length $p$ such that a word $a^{p^2}$ can be split into 5 parts $uvxyz$. I need to assume that $L$ is context-free and run through some cases and check if the word violates the pumping lemma or if it doesn't violate the pumping lemma but isn't in the language definition.

I know the concept of proving languages aren't context free and the pumping lemma but I'm very stuck applying it to this particular language.

What do I do?

• What happens when you "pump" that string of $n^2$ times $a$? How long can you make it by pumping? Can you pump it so that its length is no longer a square? – chi May 13 '16 at 13:12
• Since all of $u,v,x,y,z$ consist entirely of $a$s, this is simple. Hint: show that $uv^ixy^iz$ has length greater than $p^2$ and less than $(p+1)^2$ for some suitable value of $i$. – Rick Decker May 13 '16 at 13:17
• Possible duplicate of How to prove that a language is not context-free? – DylanSp May 13 '16 at 14:31
• @DylanSp I don't think this is a duplicate. The asker is aware of the general techniques available but is asking about a specific attempt to prove that aspecific language isn't context-free. – David Richerby May 13 '16 at 18:43

As usual in problems like this, we assume that the language $L$ is context free, so the Pumping Lemma applies, meaning that there is an integer $p>0$ such that we can write the string $a^{p^2}$ as the concatenation of strings $uvxyz$ with $|vy|>0$ and $|vxy|=t\le p$. Hence, we'll have $$0 < |vy|=t\le p$$ This means that when we pump $uvxyz$ to $uv^ixy^iz$ we'll have $$p^2<|uv^ixy^iz|=p^2+(i-1)t\le p^2+(i-1)p$$ Choosing $i=2$ gives us $$p^2<|uv^2xy^2z|\le p^2+p$$ Now, in length order, the next string in $L$ after $a^{p^2}$ will be $a^{(p+1)^2}$. Here's the hint: use this fact to show that $uv^ixy^iz$ can't possibly be in $L$, contradicting the Pumping Lemma consequence that all the pumped strings are in $L$, so consequently $L$ cannot be a CFL.
This idiom, BTW, can be used to show that other languages over a one-symbol alphabet aren't context-free, like the $a^{n^5}$ language or the $a^p$ language, where $p$ ranges over the primes. There are more general results, as well, like the one that says that any CFL over a one-symbol language is regular. That, along with another theorem that says, roughly, that a regular language over a one-symbol language can't be too "sparse", gives a higher-level proof of your question.