Pumping lemma with multiple of prime number + a constant

Question

Given the language $$L = \big\{ 0^{m} 1 0^{2m+k} \mid m \text{ prime and } k \ge 1 \big\} $$ show that $L$ is not context free by giving a counterexample of the context free pumping lemma. It may be userful the pumping lemma of the language of prime numbers, you can find it here.

A counterexample must be a string $z \in L$ whose length $|z|$ is greater than a generic h such that for any the decompositions $uvwxy=z$ with $|v|+|x|\ge 1$ and $|vwx|<h$ exists an i such that $uv^iwx^iy \not\in L$. Generally we have to find a contraddiction of $|v|+|x|\ge 1$ or $|vwx|<h$.

There are five possible decompositions of the string. The only required case is the one with $v$ completely in the first part of the string and $x$ completely in the second part.

Now follows some failed attempts:

1. This one was posted as answer I deleted because incorrect. I took as string $z = 0^{2h}10^{5h}$ which is in the language for $m = 2h$ and $k = h$. The problem here is that $m$ is prime, so $m = 2h \iff h = 1$ which means $h$ is not a generic length anymore. Here it follows the incorrect attempt:

   $$ uv^iwx^iy = 0^{2h + |v|(i-1)} 1 0^{5h + |x|(i-1)} = 0^{m} 1 0^{2m+k} \in L $$ The equation has solution iff has solution the system $$ \begin{cases} 2h + |v|(i-1) = m, m \text{ prime} \\ 5h + |x|(i-1) = 2m + k \\ \end{cases} $$ For $i = h + 1$ we have $$ 2h + h|v| = h(|v| + 2) = m $$ But $m$ cannot be prime because it's a moltiplication of two terms $h$ and $(|v| + 2)$. Contraddiction!

   We need to choose $m$ as something like $h$ or $ah + b$ in order to avoid this issue.

2. I took as string $z = 0^h 1 0^{2h+1}$ which is in the language for $m = h, k = 1$. We have $$ uv^iwx^iy = 0^{h+|v|(i-1)} 1 0^{2h + 1 + |x|(i-1)} $$ We have to solve the system $$ \begin{cases} h + |v|(i-1) = m, m \text{ prime} \\ 2h + 1 + |x|(i-1) = 2m + k\end{cases} $$

   • Trying with $i = h + 1$ does not work: the first equation becomes

     $$ h + h|v| = h(1 + |v|) = m \text{ prime} \iff |v| = 0$$ so the second equation results in $$ 2h + 1 + h|x| = 2h + k \Rightarrow |x| = \frac{k-1}{h} $$ so the string results in $0^{m} 1 0^{2m+k} \in L$ with $m = h$, $k = h + 1$ from the decomposition with $$ |v| = 0 \qquad |x| = \frac{(h+1) - 1}{h} = 1$$

   • Trying with $i = 0$ leads to

     $$ \begin{cases} h - |v| = m \\ 2h + 1 - |x| = 2m + k \end{cases}$$ which results in \begin{align*} 2h + 1 - |x| &= 2h - 2|v| + k \\ 2|v| - |x| &= k - 1 \end{align*} which results in as many string $\in L$ as you want (for example $k = 3, |x| = 0, |v| = 1$ gives $0^{h-|v|} 1 0^{2h-2|v|+1} = 0^{h-1} 1 0^{2h-1} \in L$)

3. I took the string $z = 0^{h} 1 0^{3h}$ which is in the language for $m = h, k = h$. We have $$ uv^iwx^iy = 0^{h+|v|(i-1)} 1 0^{3h + |x|(i-1)} $$ We have to solve the system $$ \begin{cases} h + |v|(i-1) = m, m \text{ prime} \\ 3h + |x|(i-1) = 2m + k\end{cases} $$

   • Trying with $i = h + 1$ we have

     $$ h = m \qquad |v| = 0 \qquad 3h + h|x| = 2h + k$$ which results in $ |x| = \frac{k}{h} - 1$; then we can take $k = 3h$ so $|x| = 2$, and the result is the string $0^{h} 1 0^{4h} \in L$

As you can see, I can't find a combination of string and $i$ that generates a contraddiction. How would you proceed?

Answer 1

Your error is that you assume that you must find one $i$ to satisfy all the subdivisions $uvwxy$ of the lemma. The lemma is actually much weaker in that you need to find any $i$ for every subdivision $uvwxy$ of a string $s$ in $L$ longer than $h$. Without loss of generality, I will assume that any given $h$ is prime, because if it were not, I would just substitude all next occurances with any higher prime number and everything would still work the same way (I never needed the condition $|vwx|\le h$).

That said you can take your second try from the question and then fork it into two cases where:

1. $v \neq \epsilon$ (where $\epsilon$ means empty string, I don't know if that's international notaion. It can be otherwise written as $|v|\neq0$ )
   From your first equation $$h + |v|(i-1) = m, m \text{ prime}$$ with $i = h + 1$ you get $$h + |v|h = (1+|v|)h$$ which is composite number because of our assumption $v \ne \epsilon$, meaning the string is not from $L$.

2. $|v|=0$ where we can pick another $i$ because it is different division of the string $s$. Here we get $$|v|=0 \land |vx| \ge 1 \implies |x|\ge 1$$ And we can trivially chose $i=0$, because now we actually subtract from the second string of zeroes, which was originally $2h+1$ long. The new length will be shorter than that, meaning we'll get a string $0^{h}10^{g}$ where $g<2h+1$ thus the string is not from the language $L$.

On final note, if you were to use this as a rigorous proof, you would need to address all the other options including those, where the $1$ is part of either of the pumped strings, it is part of either $u$ or $y$ and so on. I covered only the two interesting options and the others should now be trivial to you (I assume that is why you never mentioned them in your question and assumed that 1 is part of the $w$ string).