# Searching for a proof for a variant of the pumping lemma for context free languages

So I'm trying to understand the pumping lemma for CFL ( context free languages ).I've already used it to show that a language is not contextfree and I have considered the proof of this lemma (see the PDF below ) Now I've read that there is a variant of the pumping lemma for context free languages. You replace the condition " $$vy \neq \varepsilon$$ " with " $$v$$ and $$y$$ are not $$\varepsilon$$". Like I've said. Here is the proof of the"normal" pumping lemma for CFL.

What do I have to change for the variant of the pumping lemma?

• There are some stronger variants of the pumping lemma like the Ogden Lemma or the Bader-Moura Lemma. Concerning the variant you mention, it can certainly not be proved for the same constant. I even doubt that it is possible at all, already for the simple fact that people would probably use this stronger variant. – Peter Leupold Nov 20 '18 at 10:55
• However, my first idea was this one: Take a larger constant that guarantees the existence of two non-interleaving loops in the derivation. If one of them produces pump factors on either side, take it for the proof of the lemma as before. If both produce non-terminals only on one side, take these two factors for the pumping. Here not just all $uv^iwx^iy$ are in the language, but all $uv^iwx^ky$; but the latter of course implies the former. So this kind of pumping is maybe not in the original spirit, but it still works. – Peter Leupold Nov 20 '18 at 10:56
• The constant might be significantly bigger and more complicated to calculate for a given grammar. More importantly, you loose the condition $|vwx|<c$ for the constant c, because the two loops might be far apart. Probably you can guarantee that one loop is below the other - but this makes the calculation of the constant even more complicated. – Peter Leupold Nov 20 '18 at 10:57

There is a straightforward proof using the more common version of the pumping lemma:

$$\sphericalangle$$ CFL $$L, n\in\mathbb N, w\in L : |w|\ge n$$

$$\tilde n := \lfloor\frac{n}{2}\rfloor$$

The usual pumping lemma states that:

$$\exists u,v,x,y,z : \begin{cases} w=uvxyz \\ |vxy|\le \tilde n \\ |vx|\not=0 \end{cases} \quad \forall i\in\mathbb N\ \ uv^ixy^iz\in L$$

There are three cases for emptiness of $$v$$ and $$y$$:

• $$|v|\not=0$$ and $$|y|\not=0$$, then $$(u,v,x,y,z)$$ satisfies the lemma that is being proven.
• $$|y|=0$$, then $$(u, v, \overline x, \overline y, \overline z)$$ satisfies the lemma that is being proven: $$\overline x := \varepsilon, \overline y=v, \overline z=xz$$ $$uv^i\overline x\overline y^i\overline z=uv^iv^ixz=uv^{2i}x\varepsilon^{2i}z=uv^{2i}x\varepsilon^{2i}z\in L$$ $$|v\overline x\overline y|=2|v|\le 2\frac{n}{2}\le n$$
• $$|v|=0$$: same as the previous case.
• This proof is wrong, since the usual pumping lemma states that $|vxy| \leq n$, not $|vxy| \leq \tilde n$. Hence we cannot assume that $|v| \leq n/2$ as this proof does toward the end. – xdavidliu Jul 25 '20 at 0:58