2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ You can split the string up in exactly the ways that the statement of the lemma says you can. $\endgroup$ – David Richerby Mar 14 '17 at 9:06
1
$\begingroup$

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

$\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.