# Pumping lemma with multiple of prime number + a constant

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?

• Wasn't this question answered on Mathematics? Before you deleted it? – rici Nov 29 '17 at 22:05
• Unfortunately it was a wrong solution posted by a friend of mine, the error was in the string z=0^h 1 0^{3h} with i=0 in the second equation of the system according to my scheme: 3h - |x| = 2m + k became 3h - |x| < 2m instead of 3h - |x| > 2m. Then I thought math stackexchange was not the right place to post the question, but I didn't have enough reputation to move the question nor to ask a moderator doing it, so I decided trying in this way – incud Nov 30 '17 at 4:02
• you only need 15 rep to flag a post. – rici Nov 30 '17 at 4:50
• My fault, I misunderstood this post meta.stackexchange.com/questions/85017/… and thought I need 250rep to do that. I apologe – incud Nov 30 '17 at 7:00

## 1 Answer

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).