Q2Theory of Computation

The lemma states: for any context-free language $L$, there exists a constant $p$ (the pumping length) such that every string $s\in L$ with $|s|\ge p$ can be written as $s=uvwxy$ satisfying: (1) $|vx|>0$ (at least one of $v,x$ is non-empty), (2) $|vwx|\le p$ (the combined pumped region is bounded), and (3) $u{v}^{i}w{x}^{i}y\in L$ for all $i\ge 0$ (both $v$ and $x$ can be pumped together, the same number of times each, and the string remains in $L$).

The proof relies on converting a CFG $G$ for $L$ into Chomsky Normal Form, so every internal node of a parse tree has exactly two children, and every derivation of a string of length $n$ produces a parse tree of height $O(\log n)$ in the number of leaves relative to the branching factor, or more precisely: if $G$ has $|V|$ non-terminals, set $p=2^{|V|+1}$ (or similar bound). Then for any string $s\in L$ with $|s|\ge p$, its parse tree must have a path from root to leaf of length at least $|V|+1$ (since a binary tree of height $h$ has at most $2^h$ leaves, and we need enough leaves to spell out $s$). Since this path has more than $|V|$ non-terminal nodes but only $|V|$ distinct non-terminals exist, by the pigeonhole principle some non-terminal $A$ must repeat along this path. Let the lower occurrence of $A$ generate substring $w$, and the upper occurrence generate the larger substring $vwx$; the portion of $s$ before $vwx$ is $u$ and after is $y$, giving $s=uvwxy$. Because $A$ derives both $w$ (from the lower occurrence) and $vwx$ (from the upper occurrence via a subderivation that itself passes through $A{\Rightarrow }^{\ast }vAx{\Rightarrow }^{\ast }vwx$), the subtree rooted at the lower $A$ can be substituted in place of itself repeatedly (or removed entirely), so $A{\Rightarrow }^{\ast }{v}^{i}w{x}^i$ for any $i\ge 0$, giving $S{\Rightarrow }^{\ast }u{v}^{i}w{x}^{i}y\in L$ for all $i$. The bound $|vwx|\le p$ follows from choosing the two occurrences of $A$ to be the bottom-most repeated pair within the last $|V|+1$ nodes of the path, keeping the subtree small; and $|vx|>0$ follows because in CNF, the derivation from the upper $A$ to the lower $A$ must consume at least one step introducing a terminal-generating sibling, since CNF rules are strictly binary-branching with no unit or null productions to allow a 'do-nothing' step.

Assume, for contradiction, that $L=\{a^n{b}^n{c}^n\mid n\ge 1\}$ is context-free. Let $p$ be the pumping length guaranteed by the lemma. Choose $s=a^p{b}^p{c}^p\in L$; clearly $|s|=3p\ge p$. By the lemma, $s=uvwxy$ with $|vx|>0$, $|vwx|\le p$, and $u{v}^{i}w{x}^{i}y\in L$ for all $i\ge 0$.

Since $|vwx|\le p$, the substring $vwx$ cannot span all three blocks of $a$'s, $b$'s, and $c$'s simultaneously (spanning all three would require length at least $p+2$, to include at least the last a, all p b's, and the first c — actually more simply: since the block of $b$'s alone has length $p$, and $a$'s and $c$'s are separated by the full $b$-block, $vwx$ can touch at most two of the three distinct blocks, because touching all three would force $|vwx|\ge p+2>p$, contradicting $|vwx|\le p$).

Case analysis: If $vwx$ lies entirely within the $a$-block (or entirely within $b$'s, or entirely within $c$'s), pumping up to $i=2$ increases the count of that one symbol while leaving the other two unchanged, breaking the required equality of counts. If $vwx$ straddles the boundary between two adjacent blocks (e.g., spans some $a$'s and some $b$'s, or some $b$'s and some $c$'s), pumping with $i=2$ increases the counts of at most two of the three symbols (and by different amounts unless $v,x$ happen to add equally, which cannot hold across three total blocks), so the resulting string cannot have equal counts of $a,b,c$ or cannot preserve the required order $a^{\ast }{b}^{\ast }{c}^{\ast }$. If $vwx$ lies entirely within one block's boundary but $v$ and $x$ are both non-empty from that same single block, only that symbol's count changes. In every case, $u{v}^{2}w{x}^{2}y$ either has unequal numbers of $a$'s, $b$'s, $c$'s, or violates the required $a^n{b}^n{c}^n$ ordering pattern, so $u{v}^{2}w{x}^{2}y\notin L$.

This contradicts the pumping lemma's guarantee that $u{v}^{i}w{x}^{i}y\in L$ for all $i\ge 0$. Therefore the assumption that $L$ is context-free is false, and $L=\{a^n{b}^n{c}^n\mid n\ge 1\}$ is not context-free. This is a canonical result distinguishing context-free from context-sensitive languages: $a^n{b}^n{c}^n$ requires simultaneously tracking two independent counts, which exceeds what a single stack (context-free) can enforce, but is well within reach of an LBA (context-sensitive), and indeed a Turing Machine, as shown by the explicit TM construction for this language.