Proving that $L = \left\{a^{n^2} | n \ge 0\right\}$ is not context free with Pumping Lemma for CFG?

Question

$$L = \left\{\left. a^{n^2} \right| n \ge 0\right\}$$

I don't quite understand this problem.

Answer 1

Hint. You could use the result that, on a one-letter alphabet, a context-free language is regular. Consequently, it suffices to prove that your language is not regular, and thus the pumping lemma for regular languages suffices to solve your problem.

Answer 2

It's very easy actually! The definition of Pumping Lema is if a language is a context-free language for all strings $S\in L$ with $|S|\ge n$ ,there exists $u, v, w, x, y ∈ Σ∗,$ such that $S = uvwxy$ with:

1- $|vwx| \le n$

2- $|vx| \ge 1$

3- for all $i \ge 0$, $uv^iwx^iy \in L$

What it says in a nutshell is that in any context-free the language you can break it into five parts and pump(add) more symbols in some parts and will still generate a string that belongs to language. we need to contradict that fact to prove it's not a context-free language

Let's start by seeing the structure of the language: $L = \{λ,a,aaaa,aaaaaaaaa,...\}$ this language is so simple, it just contains the symbol $a$ so it's obvious that the middle part $|vwx|$ would contain the symbol $a$(notice it repeat by a complete square number).

we will assume that it's a context-free language that means all the rules applies. Since (1) tells us that $vwx$ could contain $a$ and (2) tells us that $vx$ contains at least one $a$ which means that $vwx$ must contain at least 1 $a$.

Now let's check (3): based on (1) and (2) $|uwy| \le n^2-1$ which means that the maximum length of $uwy$ is $n^2-1$, since $uv^iwx^iy \in L$ when i=0 then $uwy \in L$ which is not always true because if $n^2$ is a complete square that doesn't mean $n^2-1$ is also a complete square thus makes a contradiction.