Context-Free Pumping, Ogden's Lemma, and Parsing: Examples and Counterexamples

Assume for contradiction that $L$ is context-free, and let $p$ be the pumping length from [L1]. Apply the lemma to the word $a^p{b}^p{c}^p$ to obtain a decomposition $uvwxy$ with $\mathrm{\mid }vx\mathrm{\mid }\ge 1$ and $\mathrm{\mid }vwx\mathrm{\mid }\le p$.

Because $\mathrm{\mid }vwx\mathrm{\mid }\le p$, the substring $vwx$ lies inside one block or crosses only one of the two block boundaries. Pumping $v$ and $x$ therefore changes at most two of the three symbol counts, so for $i=0$ or $i=2$ the pumped word $u{v}^{i}w{x}^{i}y$ cannot still have equal numbers of $a$'s, $b$'s, and $c$'s. This contradicts [L1].

Therefore $L$ is not context-free.

In $G_{\mathrm{\varnothing }}$, the variable $B$ never derives a terminal word, so the start symbol $S$ is not generating. The emptiness test from [L1] therefore reports $L(G_{\mathrm{\varnothing }})=\mathrm{\varnothing }$.

In $G_{\mathrm{f}\mathrm{i}\mathrm{n}}$, the dependency graph is acyclic and the grammar generates exactly the three words $ac$, $ad$, and $b$. So the finiteness test from [L1] reports "finite" on this grammar.

In $G_{\mathrm{\infty }}$, the variable $A$ lies on a productive cycle through the rule $A\to aAb$, so the dependency-graph test from [L1] reports infinitude. Indeed $L(G_{\mathrm{\infty }})=\{a^n{b}^n:n\ge 1\}$ is infinite.

These three tiny inputs realize the empty, infinite, and finite outcomes of the theorem.

Take pumping length $p:=3$ and write a word of $L$ as $s^{r}q$. If $r=0$, pump the first letter of $q$; if $r=1$, pump the initial $s$; if $r\ge 2$ and $q$ is nonempty, pump its first letter. Taking $w=x=\epsilon$ gives $\mathrm{\mid }vwx\mathrm{\mid }\le 3$, and every pump remains in $L$.

Suppose $L$ were context free and let $R:=\{s{a}^i{b}^j{c}^k:i,j,k\ge 0\}$. A product of a PDA for $L$ from [L3] with a DFA for the regular language $R$ is a PDA for $L\cap R=sK$. The homomorphism deleting $s$ would then make $K$ context free by [L3], contradicting [L2].

If the word is $s^r$ with $r\ge 3$, pump $s^3$ when $r=3$ and pump $s^2$ when $r\ge 4$. Pumping never leaves exactly one initial $s$, so every pumped word again lies in $L$. Thus $L$ satisfies the ordinary CFL pumping condition.

Hence $L$ satisfies ordinary pumping but is not context free, so it refutes the claim in [L1].