Prove context-free or not context-free

Question

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

Answer 1

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.

Answer 2

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.