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

Question

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.

https://www.google.de/url?sa=t&source=web&rct=j&url=https://cs.uwaterloo.ca/~watrous/CS360.Spring2017/Lectures/10.pdf&ved=2ahUKEwjs_PfAluHeAhWCzKQKHR6BDgwQFjAKegQICRAB&usg=AOvVaw14bQTaIb205pRrv2NpsGGX

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

Answer 1

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.