Answer

Pumping Lemma for Context-Free Languages (CFL)

Statement:
Let $L$ be a context-free language. Then there exists a constant $p \ge 1$ (the pumping length) such that for every string $w \in L$ with $|w| \ge p$, $w$ can be written as

$$w = uvxyz$$

satisfying the following conditions:

1. $|vxy| \le p$ — the middle part $vxy$ is short (bounded by $p$)
2. $|vy| \ge 1$ — at least one of $v$ or $y$ is non-empty (not both empty)
3. For all $i \ge 0$: $uv^i x y^i z \in L$ — pumping $v$ and $y$ together (0, 1, 2, … times) keeps the string in $L$

---

Interpretation

• For any sufficiently long CFL string, you can find a decomposition into 5 parts such that the inner $v$ and $y$ can be "pumped" simultaneously (repeated same number of times) and the result stays in the language.
• The simultaneous pumping of $v$ and $y$ is the key difference from the regular pumping lemma (which pumps a single $y$).
• $|vxy| \le p$ means the "pumpable" region is near the center of the string (within length $p$).

---

How to Use (Proving Non-CFL)

To prove $L$ is not context-free:

1. Assume $L$ is CFL → pumping lemma holds with some $p$.
2. Choose a specific string $w \in L$ with $|w| \ge p$ (usually $w = a^p b^p c^p$ or similar).
3. Show that for every valid decomposition $w = uvxyz$ satisfying (1) and (2), there exists some $i$ such that $uv^i x y^i z
   otin L$.
4. Contradiction → $L$ not CFL.

Common Strategy: Choose $w$ so that any $vxy$ of length $\le p$ cannot span all "coordinated" parts (e.g., three blocks $a^p b^p c^p$). Pumping disrupts the balance.

---

Example Application

Prove $L = \{a^n b^n c^n \mid n \ge 0\}$ is not CFL.

1. Let $p$ be pumping length. Take $w = a^p b^p c^p \in L$, $|w| = 3p \ge p$.
2. By lemma, $w = uvxyz$ with $|vxy| \le p$, $|vy| \ge 1$.
3. Since $|vxy| \le p$, the substring $vxy$ cannot contain $a$'s, $b$'s, and $c$'s simultaneously — it lies within at most two adjacent blocks.
4. Cases:
   • $vxy$ only in $a$'s: pumping adds $a$'s → $#a
     eq #b = #c$ ❌
   • $vxy$ only in $b$'s: pumping adds $b$'s → $#b
     eq #a, #c$ ❌
   • $vxy$ only in $c$'s: pumping adds $c$'s ❌
   • $vxy$ spans $a^p b^p$ boundary: pumping changes $\#a$ and $\#b$ differently (or adds both) → $#a
     eq #b$or$#b
     eq #c$ ❌
   • $vxy$ spans $b^p c^p$ boundary: similar ❌
5. All decompositions fail for some $i
   e 1$. Contradiction.

---

Contrast with Regular Pumping Lemma

Aspect	Regular (Type-3)	CFL (Type-2)
String split	$w = xyz$	$w = uvxyz$
Pumped part	$y$ (single)	$v$ and $y$ (pair)
Constraint	$|xy| \le p$	$|vxy| \le p$
Non-empty	$|y| \ge 1$	$|vy| \ge 1$
Result	$xy^i z \in L$	$uv^i x y^i z \in L$

---

Important Notes

• The lemma gives necessary but not sufficient condition for CFL.
• There are non-CFL languages that satisfy the lemma (e.g., some non-context-free languages still pump).
• For CFL, pumping is simultaneous of two substrings ($v$ and $y$), reflecting stack push/pop pairing.
• The pumping length $p$ depends on the grammar (e.g., number of variables in Chomsky Normal Form).

---

Final Answer

Pumping Lemma for CFL: $\exists p \ge 1$ such that $\forall w \in L, |w| \ge p$, $w = uvxyz$ with $|vxy| \le p$, $|vy| \ge 1$, and $\forall i \ge 0, uv^i x y^i z \in L$. Used to prove languages like $\{a^n b^n c^n\}$ are not context-free.