I have a proof that there is no context-free language that can produce all (and only) prime numbers. But, as context-free languages are not closed under complement, I have not found that there isn't possible to express the language L that produces all composite numbers.

For all purposes, numbers are in unary and the terminal symbol is 1.

The proof that there is no CFL that produces all prime numbers and no composite numbers I got here (in portuguese). I just used the pumping lema for CFL:

Take a prime number $N \in L$. $N$ is such that it can be expressed as a word concatenation of $u v w x y$, where $\left|v x\right| \ge 1$ and $\left|v w x\right| \le p$. So any word in the form of $u v^n w x^n y \in L, n \ge 0$.

Therefore, there are two possibilities:

  • $\left|u w y\right| = 0$, or
  • $\left|u w y\right| \gt 0$

If the first case is true, than for $n = 2$ I got $u v^2 w x^2 y$ also in $L$, but as $\left|u w y\right| = 0$, than it implies that $2N \in L$, so $L$ produces a non-prime number.

For the other case, if I pick $n = \left|u w y\right|$ I got the word $u v^{u+w+y} w x^{u+w+y} y$ that should be also in $L$. So, as this is a number in unary notation, that implies that $u + v\cdot\left(u + w + y\right) + w + x\cdot\left(u + w + y\right) + y$ should also be in $L$. So, that implies that $\left(u + w + y\right)\cdot\left(v + x + 1\right)$ is also a prime number, but it is indeed a non-prime.

In this final paragraph, I ommited some $\left|u\right|$ for the sake of readability, but intention should be clear to the reader.


By the pumping lemma, the lengths of words generated by a context free grammar are a semilinear set. If the alphabet has one symbol only, that means the language is regular. But then it's complement (i.e. the primes) would be regular too, contradiction.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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