Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
up vote 5 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.