Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

1 Answer 1

up vote 3 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|improve this answer

Your Answer

 
discard

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.