6
$\begingroup$

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!

1 Answers 1

15

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.

  • 0
    You could also use a larger $p$ to avoid the special cases. (Although I like the way you resolve the special cases, particularly the second one...)2016-08-02