Pumping Lemma CFL

Question

For proving a language is not CF, I was wondering when we split up the string to 5 pieces are we allowed to proportion it anyway as long as we satisfy the following conditions :

\begin{align} |vwx| &\le p \text{ (pumping length)}\\ |vx| &> 0 \end{align}

Could I possibly make the $u$ value take on a majority of the string?

Answer 1

From the pumping lemma for context free languages from Wikipedia, $$(\forall L\subseteq \Sigma^*)(\text{context free}(L)\implies\\ ((\exists p\ge1)((\forall s\in L)((|s| \ge p)\implies\\((\exists u,v,w,x,y\in\Sigma^*)\\(s=uvwxy \land |vwx|\le p \land |vx|\ge1 \land(\forall n\ge0)(uv^nwx^ny\in L))))))) $$

Let $i$ be the statement $$\text{context free}(L)$$ and $j$ be the statement $$((\exists p\ge1)((\forall s\in L)((|s| \ge p)\implies\\((\exists u,v,w,x,y\in\Sigma^*)\\(s=uvwxy \land |vwx|\le p \land |vx|\ge1 \land(\forall n\ge0)(uv^nwx^ny\in L))))))$$

The pumping lemma states that $i\implies j$ is true for all context free languages. Its contrapositive is $\neg j\implies \neg i$. To show that a given language is not context free using the pumping lemma, you assume that $i$ is true, then show that $\neg j$ is true, which implies that $\neg i$ is true, leading to a contradiction.

So, $\neg j$ is, $$((\forall p\ge1)((\exists s\in L)((|s| \ge p)\implies\\((\forall u,v,w,x,y\in\Sigma^*)\\\neg(s=uvwxy \land |vwx|\le p \land |vx|\ge1 \land(\forall n\ge0)(uv^nwx^ny\in L))))))$$

which gives $$((\forall p\ge1)((\exists s\in L)((|s| \ge p)\implies\\((\forall u,v,w,x,y\in\Sigma^*)\\(\neg(s=uvwxy) \lor \neg(|vwx|\le p) \lor \neg(|vx|\ge1) \lor \neg((\forall n\ge0)(uv^nwx^ny\in L)))))))$$

Note that the contrapositive of $j$ needs that at least one of the statements of the lemma be false for all ways to split strings $s$ in $uvwxy$. So, you need to consider all possible ways in which they can be split.

---

If the statements are not clear, the following is an alternative:

$i$:

The language $L$ is context free.

$j$:

There exists $p\ge1$ such that for all strings $|s|\in L$ and $s\ge p$, there exists a way to split $s$ as $uvwxy$ such that

1. $|vwx|\le p$
2. $|vx|\ge1$
3. $uv^nwx^ny\in L$ for all $n\ge 0$

which gives $\neg j$ to be

For all $p\ge1$, there exists string $s\in L$ and $|s|\ge p$, such that for all ways to split $s$ as $uvwxy$, at least one of the following is false

1. $|vwx|\le p$
2. $|vx|\ge1$
3. $uv^nwx^ny\in L$ for all $n\ge 0$

Note that the statement uses "for all ways to split $s$ as $uvwxy$", and hence, you cannot make assumptions on the length of $u$.