Language of words $1^k$ where $k$ is not a prime

Question

Is the language

$$\{1^k:k\text{ is not a prime number}\}$$

a context free language?

If, not how can I prove this using the pumping lemma for context free languages?

Answer 1

I claim that this language (call it $L$ for convenience) is not context-free.

Suppose for the sake of contradiction that $L$ is context-free, and let $N$ be its pumping length. Choose a prime $p>\min(N, 3)$. By Wilson's theorem, $p$ divides $(p-1)!+1$. Since $p>3$, $(p-1)!+1>p$; thus $(p-1)!+1$ is composite.

Now, $(p-1)!+1$ is composite, so $1^{(p-1)!+1} \in L$. It is larger than $N$, we can apply the pumping lemma to obtain a decomposition $$1^{(p-1)!+1}=1^a1^b1^c1^d1^e$$ where $1 \leq b+d \leq N$, and $1^a1^{kb}1^{c}1^{kd}1^e \in L$ for all integers $k \geq 0$.

In other words, we have five nonnegative integers $a,b,c,d,e$ such that $(p-1)!+1=a+b+c+d+e$, $1 \leq b+d \leq N$, and $a+kb+c+kd+e=(a+c+e)+k(b+d)$ is composite for all integers $k \geq 0$.

But since $b+d \leq N \leq p-1$, $b+d$ and $(p-1)!+1$ are coprime. It follows that $b+d$ and $a+c+e=(p-1)!+1-(b+d)$ are also coprime. So, by Dirichlet's theorem on arithmetic progressions, the arithmetic progression $a+c+e+k(b+d)$ contains infinitely many primes. We have reached a contradiction; thus $L$ is not context-free.