# Is there a context-free language that can produce all the composite numbers?

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.