0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Wasn't this question answered on Mathematics? Before you deleted it? $\endgroup$ – rici Nov 29 '17 at 22:05
  • $\begingroup$ 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 $\endgroup$ – incud Nov 30 '17 at 4:02
  • $\begingroup$ you only need 15 rep to flag a post. $\endgroup$ – rici Nov 30 '17 at 4:50
  • $\begingroup$ My fault, I misunderstood this post meta.stackexchange.com/questions/85017/… and thought I need 250rep to do that. I apologe $\endgroup$ – incud Nov 30 '17 at 7:00
1
+100
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.