Pumping lemma (CFL): aⁿbⁿcⁿ not CF

Pumping lemma for CFLs: if L is context free, there is a constant p such that every s ∈ L with |s| ≥ p can be written s = uvxyz with (1) |vxy| ≤ p, (2) |vy| ≥ 1, (3) uvⁱxyⁱz ∈ L for all i ≥ 0.

Proof that L = { aⁿbⁿcⁿ : n ≥ 0 } is not context free

Assume L is context free, with pumping length p.

1. Choose s = aᵖbᵖcᵖ. Then s ∈ L and |s| = 3p ≥ p.
2. Let s = uvxyz satisfy the lemma. Since |vxy| ≤ p, the substring vxy cannot contain both an a and a c (between the last a and the first c there are p b's). So vxy has at most two kinds of letters, and some letter among a, b, c does not appear in vxy.
3. The letters in v and y come from at most two of a, b, c, and |vy| ≥ 1. Pumping changes the counts of only those letters; the missing letter keeps count p.
4. Take i = 2 (pumping up). Because |vy| ≥ 1, at least one letter count increases above p, while at least one letter (the one not in vxy) keeps count exactly p. Hence the counts of a, b, c are not all equal.
5. If v or y contains two different letters, uv²xy²z also has letters out of the order a…b…c.

In every case uv²xy²z ∉ L, which contradicts condition (3).

Therefore the assumption is false: L = { aⁿbⁿcⁿ } is not context free.

(It is context sensitive. A single stack can compare two counts, but it cannot check three equal counts, since popping destroys the count.)