# 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

## 4 Answers

[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.

Assume that the language $$L = \{a^{(n^2)} | n > 0\}$$ is context-free and let N be the pumping length given by the Pumping Lemma.

Choose the string $$u = a^{(N^2)}$$, which is in the language L. According to the Pumping Lemma, u can be decomposed into vwxyz such that |wxy| ≤ N, |wy| > 0, and $$vw^mxy^mz$$ is in L for every $$m ≥ 0$$.

When you choose m = 2, you pump the substring wxy, which increases the length of the string.

The length of the pumped string $$vw^2xy^2z$$ becomes $$(N + n)^2$$, where $$n \in \mathbb{N}$$. Now we now that |wy| = j + k, |w| = j, and |y| = k.

Now we know that this must be true $$(N + n)^2 = N^2 + j+ k$$.

From this equation, you deduce that $$j + k = 2Nn + n^2$$, which is greater than N since n > 0.

This contradicts the Pumping Lemma's requirement that |wxy| ≤ N.

Therefore, the assumption that L is context-free must be incorrect.Thus, you conclude that the language $$L = \{a^{(n^2)} | n > 0\}$$ is not context-free.

• This proof attempt is seriously flawed. The length of $vw^mxy^mz$ is $N+(m-1)n$. One needs to find an $m$ such that $N+(m-1)n$ is not a square.
– Kai
Aug 31, 2023 at 22:38
• @kai You' re right, my bad, indeed the length of the pumped string is N+n , where n is a natural number. Now we have to prove that $N^2+j+k$ is not a square, but equivalently we can prove that $|wy|\geq N$ so the HP that $|wxy|\leq N$ is not satisfied. Sep 1, 2023 at 11:14