# How to use the Pumping Lemma to show that a language is not context free?

I have the following alphabet $$\Sigma = \{0,\dots,9\}$$ and the following language over $$\Sigma \cup \{\#\}$$: $$L=\{\#w \ |\ w \in\Sigma^*,\sum_{i\geq1}w_i\ \text{is prime}\}\\\\$$ This language represents all numbers wich have a prime as digit sum. I now want to show that this language is not context free. I want to show this with a reductio ad absurdum via the pumping lemma and I am not quite sure if I proofed it correctly:

My idea was to just pick a word wich is in $$L$$ and then show that it cannot be pumped up with the pumping lemma and because if the language is context free every word can be pumped up this shows that $$L$$ is not context free. But I am not quite sure if this is enough.

Let's assume that L is context free. Then the pumping lemma states that there is a number $$k \in \mathbb{N}$$ for wich every word $$w \in L$$ with $$|w|\geq k$$ can be splitted up like the following $$w=xuyvz$$ where the following constraints hold:

• $$0<|uv|\leq|uyv|\leq k$$
• $$\forall n \in \mathbb{N}:xu^nyv^nz \in L$$

Let $$k=5$$ and $$w=\#11111$$ because $$|w|=6 \Rightarrow |w|\geq k$$. We can split up $$w$$ like this $$w=xuyvz$$ where the following holds:

• $$x=\#$$
• $$u=1$$
• $$y=11$$
• $$v=1$$
• $$z=1$$

Because $$|uv|=2 \ \land \ |uyv|=4 \Rightarrow 0<|uv|\leq|uyv|\leq k$$. Now $$\forall n \in \mathbb{N}:xu^nyv^nz \in L$$ should also be true. But let $$n=3$$ then $$w'=\#111111111 \notin L$$. Thus $$L$$ is not context free, because the pumping lemma with a number $$k \in \mathbb{N}$$ is not working for every $$w$$ with $$|w|\geq k$$.

I am self learning and have no one who can help me with this, so I really would appreciate if someone could tell me if this proof is working or how I can improve it.

• It is unclear what "$\sum\limits_{i\geqslant 0}^{10}w_i \text{ is prime}$" means. Does that mean "the sum of the first eleven digits of $w$ is prime"? But it is inconsistent with the following sentence. Please clarify. Commented Jan 9, 2023 at 18:08
• Oh the 10 wasn't supposed to be there. It should mean that the sum of every number is prime. I edited the question. Commented Jan 10, 2023 at 13:51

There are several problems in your proof. The language $$L$$ indeed is not context-free, and the pumping lemma can be used to prove it.

However:

• you cannot choose the value of $$k$$ yourself;
• you cannot choose the values of $$x, u, y, v$$ and $$z$$ yourself.

The pumping lemma states that if $$L$$ is context-free, then THERE EXISTS $$k\in \mathbb{N}$$ such that FOR ALL $$w\in L$$ with $$|w| \geqslant k$$, then THERE EXISTS a decomposition $$w=xuyvz$$ verifying the three conditions.

However, to prove that $$L$$ is not context-free, you have to use the contraposition:

If FOR ALL $$k\in \mathbb{N}$$, THERE EXISTS $$w\in L$$ with $$|w| \geqslant k$$ such that FOR ALL decompositions $$w=xuyvz$$, not all three conditions are verified, then $$L$$ is not context-free.

The formulation you have seen may be a bit different, but the same ideas are underlying.

Now back to your problem. Let $$k\in\mathbb{N}$$ be any integer. Consider $$p$$ any prime number $$\geqslant k$$. Given the definition of $$L$$, it is clear that $$w = \#1^p\in L$$ (here the $$^p$$ denotes $$p$$ repetitions, not the mathematical exponentiation).

Suppose $$w = xuyvz$$ with $$|uv| >0$$ and $$|uyv|\leqslant p$$. Let us distinguish:

• if $$uv$$ contains the symbol $$\#$$, then $$xyz$$ does not contain $$\#$$ so $$xyz\notin L$$;
• that means that $$uv = 1^q$$ with $$0. Then, $$xu^{p+1}yv^{p+1}z = xuyvz(uv)^p = \#1^p1^{qp} = \#1^{q(p+1)}$$. However, $$q(p+1)$$ is not prime, so $$xu^{p+1}yv^{p+1}z\notin L$$.

We conclude that $$L$$ is not context-free.