Prove context-free or not context-free Given the following language:
$L=\{a^{p^2}|$ $p$ is prime$\}$
How can I show that this language is not context free using the pumping lemma?
I'm having trouble breaking it up to $s = uvxyz$.
would love to get some help. 
thanks
 A: Let
$$
P_2 \equiv \{p^2 : p \text{ is prime}\}.
$$
Thus, $L\equiv \{a^r: r\in P_2\}$.
Suppose $L$ is context free. Then by the pumping lemma, there is an integer $q$ such that for all $s\in L$ with $|s|\ge q$, there exist $u,v,x,y,z$ with 


*

*$s=uvxyz$,

*$|vxy|\le q$,

*$|vy|\ge 1$, and

*$uv^nxy^nz\in L$ for all $n\ge 0$.


Take such an $s,u,v,w,x,y,z$. Obviously, we can write $u=a^{r_u}$, $v=a^{r_v}$, $x=a^{r_x}$, $y=a^{r_y}$, and $z=a^{r_z}$ for some constants $r_u,r_v,\ldots$. Since $|vy|\ge 1$, it follows $r_v+r_y>0$. And since $uv^nxy^nz\in L$ for all $n\ge 0$, it follows that for all $n\ge 0$,
$$
r_u + r_x + r_z + n(r_v + r_y) \in P_2.
$$
This later statement cannot be true. To see this, let $p,p'$ be two consecutive primes. Then $\delta\equiv p'-p\ge 2$, so $p'^2 - p^2 = (p+\delta)^2 - p^2 = 2p\delta + \delta^2\ge 4p+4$. Thus, the gap between the squares of consecutive primes grows without bound, so there can be no infinitely long arithmetic progression among $P_2$.
By contradiction, $L$ is not context free.
A: You could use Parikh's theorem which implies that any context-free language of $a^*$ is regular. Then it suffices to use the pumping lemma for regular languages to show that $L$ is not regular. I let you do this part, which is pretty easy.
