# 2.3 Pumping Lemma for CFL

## Definition of Pumping Lemma

Let $L$ be a context-free language. Then there is a constant $p$ so that if $z \in L$ and $|z| \geq p$ then $z$ can be decomposed into 5 parts: $z = uvwxy$. so that:

• $|vwx| \leq p$
• $vx \not = \varepsilon$
• $\forall i, uv^i wx^i y \in L$

## An non-CFL to prove that cannot be pumped

Suppose it is context free. Let p be its pumping constant. Let $z = 0^p 1^p 2^p$ be a string longer than p and in the language. Suppose we have a decomposition $uvwxy$, where $|vwx| \leq p$, so $uwx$ cannot include all three letters because it is too short.

then we pumped the string to $uv^2 wx^2 y$, which cannot be in the language. Because the letter that cannot be covered in $uwx$ cannot get repeated then there is less numbers of it in the new string.

So $uv^2 wx^2 y$ is not in the language, which contradicted to the pumping lemma.

## An non-CFL that can be pumped

### L is not CFL

Suppose L is context free. We know that $ab*c*d*$ is a regular language R. Then the intersection $L \cap R$ should also be context-free. However, $L \cap R = \{ab^j c^j d^j | j \geq 0\}$, which is not context-free. Contradiction.

### L can be pumped

First of all, $L_1$ and $L_3$ are regular languages, so all strings in them can be pumped.

Let p be the pumping constant of $L_2$, $z = a b^p c^p d^p$, no matter what the value of $vwx$ is, the pumped string $uv^2 w x^w y$ can belong to $L_3$, which is still in L. So L is pumpable.