# 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, 2016 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$. May 13, 2016 at 13:17
• Possible duplicate of How to prove that a language is not context-free? May 13, 2016 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. May 13, 2016 at 18:43

[Since (a) this is an instance of a standard problem and (b) I wasn't able to find it in the archives, I'll expand my comment into a hinted solution.]

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.

## If still have your question, I thought this might help why using pump up i=2 we can show the language is not Context Free.

Let $$s=a^{p^2}$$

next string is for (n+1) : $$s=a^{(p+1)^2}$$

$$s=uvxyz; |vxy|\leq P;|vy|\geq1$$

at most length $$|vy|=p$$ pump up i=2 so the pumped string $$p^2+p$$ which is not in the language because: $$(p+1)^2$$>$$(p^2+p)$$ so the language given is not context-free.

A unary language (a language over a unary alphabet) is context-free iff it is regular. Moreover, such a language is context-free (or regular) iff the set of lengths of words in the language is eventually periodic.

The set $$\{n^2 : n \in \mathbb{N}\}$$ is not eventually periodic: the gap between adjacent elements increases without bound. So the language $$\{a^{n^2} : n \in \mathbb{N}\}$$ isn't regular or context-free.