I have a hunch that the language $L = \{ x^n : n \text{ is prime.} \}$ is not context-free. I am trying to show that by contradiction with the Pumping Lemma:
First assume that $L$ is context-free. That means for any string in $L$ of a certain pumping length $p$ or greater, that string can be broken into $s = uvxyz$ where $|vxy| \le p$, $|vy| > 0$, and $uv^ixy^iz$ is in $L$ where $i$ can be any natural number including 0.
I first tried letting $s = x^P$. However, I'm not quite sure how to divide this value up into $uxvyz$ to show that it cannot be pumped. Any advice?
This is not homework. I am practicing on my own. Thanks!
Best Answer
Let $v=x^q$ and $y=x^t$, noting the pumping lemma requires $q+t>0$. Let $r=|uxz|=p-q-t$. Then $$|uv^rxy^rz|=r+rq+rt=r(1+q+t)$$ is divisible by both $r$ and $1+q+t>1$ and thus is not prime as long as $r>1$.
Then there are two unsettled cases: if $r=0,$ $$|uv^2xy^2z|=|v^2y^2|=2p$$ is not prime. Finally, if $r=1,$ $$|uv^{p+1}xy^{p+1}pz|=1+(p+1)q+(p+1)t=1+(p+1)(q+t)=1+(p+1)(p-1)=p^2$$ isn't prime.