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

Question

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.

Answer 1

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<q\leqslant p$. 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.