Context-Free Pumping, Ogden's Lemma, and Parsing

We induct on the height $h$. If $h=1$, then the root is already a leaf. By [L1], a leaf at the root can only be the variable leaf corresponding to the exceptional CNF rule $S\to \epsilon$ from [L2]. Thus $y(T)=\epsilon$, so $\mathrm{\mid }y(T)\mathrm{\mid }=0\le 1=2^0$.

Suppose $h>1$. If the root uses a terminal production $A\to a$, then the yield has length $1$, so the bound is immediate. Otherwise the root uses a binary production $A\to BC$ by [L2]. The two child subtrees have heights at most $h-1$, so by the induction hypothesis each contributes at most $2^{h-2}$ terminal leaves. Therefore $\mathrm{\mid }y(T)\mathrm{\mid }\le 2^{h-2}+2^{h-2}=2^{h-1}$.

The bound holds for height $1$ and is preserved when the height increases, so every CNF parse tree of height $h$ has yield length at most $2^{h-1}$.

Choose a CNF grammar $G^{\mathrm{\prime }}=(V,\mathrm{\Sigma },P,S)$ with $L(G^{\mathrm{\prime }})=L$ by [L1] and [L2], and let $m:=\mathrm{\mid }V\mathrm{\mid }$. Set $p:=2^{m+1}+1$. Let $z\in L$ satisfy $\mathrm{\mid }z\mathrm{\mid }\ge p$. By [L3], $z$ is the yield of some parse tree $T$ for $G^{\mathrm{\prime }}$. If every root-to-leaf path of $T$ had at most $m$ variable nodes, then $T$ would have height at most $m+1$, so [L4] would give $\mathrm{\mid }z\mathrm{\mid }\le 2^m<p$, contradicting $\mathrm{\mid }z\mathrm{\mid }\ge p$. Therefore some root-to-leaf path has at least $m+1$ variable occurrences.

Choose two equal variables $A$ on the last $m+1$ variable occurrences of such a path, with the upper one above the lower one. Let the yield of the upper $A$-subtree be $vwx$ and the yield of the lower $A$-subtree be $w$, so the whole word is $uvwxy$. Because the lower occurrence lies strictly below the upper one and $G^{\mathrm{\prime }}$ is in CNF, the path segment from the upper $A$ to the lower one cannot consist only of unit moves, so at least one of the side contexts $v$ and $x$ is nonempty. Hence $\mathrm{\mid }vx\mathrm{\mid }\ge 1$. The upper $A$-subtree contains at most the last $m+1$ variable occurrences on the path, so its height is at most $m+2$; therefore [L4] gives $\mathrm{\mid }vwx\mathrm{\mid }\le 2^{m+1}<p$.

The parse-tree segment from the upper occurrence of $A$ down to the lower one shows that $A{\Rightarrow }^{\ast }vAx$, and the lower subtree shows $A{\Rightarrow }^{\ast }w$. Repeating or deleting the first derivation segment any number of times while keeping the rest of the tree fixed yields derivations of $u{v}^{i}w{x}^{i}y$ in $G^{\mathrm{\prime }}$ for every $i\ge 0$. Hence every such word lies in $L(G^{\mathrm{\prime }})=L$.

Therefore the integer $p$ satisfies the required pumping property.

Choose a context-free grammar $G_0$ with $L(G_0)=L$ by [L2], then replace it by an equivalent Chomsky-normal-form grammar $G=(V,\mathrm{\Sigma },P,S)$ by [L3]. Set $p:=2^{\mathrm{\mid }V\mathrm{\mid }+1}$. Let $z\in L$ and mark at least $p$ positions of $z$. Because $p\ge 1$, the word $z$ is nonempty, so by [L4] fix a parse tree $T$ for $z$ in the CNF grammar $G$.

Starting at the root of $T$, build a path to a marked leaf by always moving to a child whose subtree contains the larger number of marked positions; when both children contain marked positions, choose one of the heavier children. Call such a node a branch point. Each time the path passes through a branch point, the chosen child still contains at least half of the marked positions seen at that node. Therefore, if there were at most $\mathrm{\mid }V\mathrm{\mid }$ branch points on the path, the terminal leaf at the end would still lie below at least $p\mathrm{/}{2}^{\mathrm{\mid }V\mathrm{\mid }}=2$ marked positions, impossible for one leaf. So the path contains at least $\mathrm{\mid }V\mathrm{\mid }+1$ branch points.

Among the last $\mathrm{\mid }V\mathrm{\mid }+1$ branch points on that path, choose two with the same variable label $A$, with the upper one above the lower one. Let the lower $A$-subtree yield $w$, and let the material in the upper $A$-subtree to the left and right of the lower subtree yield $v$ and $x$, so that the whole word is $z=uvwxy$. The upper branch point has marked material outside the lower subtree, so the concatenation $vx$ contains a marked position. Also, if the upper $A$-subtree contained more than $2^{\mathrm{\mid }V\mathrm{\mid }}$ marked positions, then repeating the branch-point-halving argument inside that subtree would produce more than $\mathrm{\mid }V\mathrm{\mid }$ branch points below it on the chosen path, contradicting that we selected the upper $A$ among the last $\mathrm{\mid }V\mathrm{\mid }+1$ branch points. Hence $vwx$ contains at most $2^{\mathrm{\mid }V\mathrm{\mid }}<p$ marked positions. By [L1], the decomposition is $p$-admissible.

The upper occurrence of $A$ derives the lower one by a derivation segment $A{\Rightarrow }^{\ast }vAx$, and the lower subtree derives $w$. Repeating or deleting that segment while keeping the rest of the parse tree fixed produces derivations of $u{v}^{i}w{x}^{i}y$ for every $i\ge 0$. Therefore every such word lies in $L(G)=L$.

Hence the integer $p$ satisfies Ogden's lemma for $L$.

The grammar $S_1\to AB$, $A\to aAb\mid \epsilon$, $B\to cB\mid \epsilon$ generates $L_1$, and the grammar $S_2\to CD$, $C\to aC\mid \epsilon$, $D\to bDc\mid \epsilon$ generates $L_2$. Therefore both languages are context-free by [L1].

A word belongs to $L_1\cap L_2$ exactly when its number of $a$'s equals its number of $b$'s and its number of $b$'s equals its number of $c$'s. Hence $L_1\cap L_2=\{a^n{b}^n{c}^n:n\ge 0\}$.

Suppose $L_1\cap L_2$ were context-free. Let $p$ be the pumping length from [L2], and consider the word $a^p{b}^p{c}^p$. Any factor $vwx$ with $\mathrm{\mid }vwx\mathrm{\mid }\le p$ lies within 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 word $u{v}^{i}w{x}^{i}y$ cannot still have equal numbers of $a$'s, $b$'s, and $c$'s. This contradicts [L2].

Thus $L_1\cap L_2$ is not context-free even though each of $L_1$ and $L_2$ is. So context-free languages are not closed under intersection.

Assume for contradiction that context-free languages were closed under complement. Then the complements $A^c$ and $B^c$ of context-free languages would again be context-free.

By [L2], the union $A^c\cup B^c$ would then be context-free, and by the contradiction hypothesis its complement would be context-free as well. By [A1], that complement is exactly $A\cap B$. So the contradiction hypothesis would force closure under intersection.

This contradicts [L1]. Therefore context-free languages are not closed under complement.

Choose a grammar $G=(V,\mathrm{\Sigma },P,S)$ with $L=L(G)$ by [L2]. Define a new grammar $G^R=(V,\mathrm{\Sigma },P^R,S)$ by putting a production $A\to {\alpha }^R$ in $P^R$ whenever $A\to \alpha$ belongs to $P$. This is again a context-free grammar by [L1].

Mirror every parse tree of $G$ by reversing the left-to-right order of the children at each internal node. The mirrored tree uses exactly the reversed productions from step 1.1, so by [L4] it is a parse tree of $G^R$. Its yield is the reversal of the original yield, by [L3]. Therefore $w\in L$ implies $w^R\in L(G^R)$. Mirroring back proves the converse implication.

Hence $L(G^R)=L^R$, so $L^R$ is context-free by [L2].

We induct on the span length $\mathrm{\ell }$. For $\mathrm{\ell }=1$, [L1] says that $A\in T[i,1]$ exactly when $A\to a_i$ is a production, and by [L2] that is exactly when $A{\Rightarrow }_G^{\ast }{a}_i$.

Assume the claim known for all shorter spans and let $\mathrm{\ell }\ge 2$. If $A\in T[i,\mathrm{\ell }]$, then [L1] provides a split $k$ and a production $A\to BC$ with $B\in T[i,k]$ and $C\in T[i+k,\mathrm{\ell }-k]$. By the induction hypothesis, $B{\Rightarrow }_G^{\ast }{a}_i\cdots a_{i+k-1}$ and $C{\Rightarrow }_G^{\ast }{a}_{i+k}\cdots a_{i+\mathrm{\ell }-1}$, so one use of $A\to BC$ followed by those derivations gives $A{\Rightarrow }_G^{\ast }{a}_i\cdots a_{i+\mathrm{\ell }-1}$.

Conversely, suppose $A{\Rightarrow }_G^{\ast }{a}_i\cdots a_{i+\mathrm{\ell }-1}$ with $\mathrm{\ell }\ge 2$. Because $G$ is in CNF, the first derivation step from $A$ must be a binary production $A\to BC$, and the derived word must split at some $k$ into a prefix from $B$ and a suffix from $C$. The induction hypothesis then gives $B\in T[i,k]$ and $C\in T[i+k,\mathrm{\ell }-k]$, so [L1] places $A$ in $T[i,\mathrm{\ell }]$.

Steps 1.1, 2.1, and 2.2 prove the equivalence for every cell.

If $w=\epsilon$, then by the definition of Chomsky normal form the only way to derive $\epsilon$ is the exceptional start production $S\to \epsilon$. So the empty-word branch is correct.

Suppose $w=a_1\cdots a_n$ is nonempty. By [L1], the condition $S\in T[1,n]$ is equivalent to $S{\Rightarrow }_G^{\ast }w$. By [L2], that is equivalent to $w\in L(G)$. Therefore the table branch accepts exactly the generated nonempty words.

The two branches together decide membership in $L(G)$.

Convert $G$ to an equivalent CNF grammar $G^{\mathrm{\prime }}$ using [L1].

Run the CYK membership procedure from [L2] on $G^{\mathrm{\prime }}$ and $w$. Because $G^{\mathrm{\prime }}$ is equivalent to $G$, the answer is "yes" exactly when $w\in L(G)$.

Therefore context-free-language membership is decidable.

To decide emptiness, compute the least set of generating variables: start with variables that have a production to a terminal word, and repeatedly add a variable $A$ once some production $A\to \alpha$ has every variable occurring in $\alpha$ already marked generating. Because $V$ is finite, this fixed-point computation halts. By [L1], the language is empty exactly when the start variable $S$ never becomes generating.

For finiteness, first replace $G$ by an equivalent grammar $G^{\mathrm{\prime }}$ using [L2], [L3], and [L4], so that every remaining variable is useful, there are no unit productions, and there are no epsilon-productions except possibly the start-symbol exception. Build the directed dependency graph on the variables of $G^{\mathrm{\prime }}$ with an edge $A\to B$ whenever some production for $A$ contains $B$ on its right-hand side.

If some reachable variable $A$ lies on a directed cycle of this graph, then usefulness gives a terminal derivation from each variable on the cycle, while the removal of unit and nonstart epsilon-productions forces at least one terminal symbol to be added when the cycle is traversed once. Hence there is a derivation $A{\Rightarrow }_{G^{\mathrm{\prime }}}^{\ast }xAy$ with $\mathrm{\mid }xy\mathrm{\mid }\ge 1$. Repeating that cycle any number of times and then finishing to terminals yields words of arbitrarily large length in $L(G^{\mathrm{\prime }})=L(G)$, so the language is infinite.

Conversely, if the reachable part of the dependency graph is acyclic, then no root-to-leaf path in a parse tree can repeat a reachable variable. So parse trees have uniformly bounded depth. Because $G^{\mathrm{\prime }}$ has only finitely many productions and bounded branching, only finitely many parse trees can occur, and therefore only finitely many terminal yields occur. Thus $L(G)$ is finite.

Step 1.1 decides emptiness, and steps 2.1-2.2 decide finiteness by a finite graph-cycle test.

We verify the ordinary pumping condition with pumping length $p:=3$. Let $z=s^{r}q\in L$ have length at least $3$, with $q\in \{a,b,c{\}}^{\ast }$. If $r=0$, pump the first letter of $q$. If $r=1$, then $q\in K$, and pump the unique initial $s$. If $r\ge 2$ and $q$ is nonempty, pump its first letter. In all three cases take the pumped letter as $v$ and take $w=x=\epsilon$; pumping preserves membership because it either keeps $r\mathrm{\ne }1$ or changes the single initial $s$ to $s^i$, which belongs to the second part of $L$ for every $i\mathrm{\ne }1$.

Suppose for contradiction that $L$ were context free. Let $R:=\{s{a}^i{b}^j{c}^k:i,j,k\ge 0\}$, which is regular. Choose a PDA for $L$ using [L3] and a DFA for $R$. The product control consisting of the PDA state and DFA state, with the same stack operation as the PDA and with epsilon moves leaving the DFA state fixed, is a PDA for $L\cap R$. Hence $L\cap R$ is context free.

It remains to treat $z=s^r$ with $r\ge 3$. For $r=3$, take $v=s^3$; for $r\ge 4$, take $v=s^2$. Put $u=w=x=\epsilon$ and let $y$ be the remaining suffix. Pumping produces respectively $s^{3i}$ or $s^{r+2(i-1)}$, whose exponent is never $1$. Thus $\mathrm{\mid }vx\mathrm{\mid }\ge 1$, $\mathrm{\mid }vwx\mathrm{\mid }\le 3$, and every pumped word lies in $L$.

By definition, $L\cap R=sK$. Apply the homomorphism that deletes the initial symbol $s$ and fixes $a,b,c$. Closure under homomorphism from [L3] would make $K$ context free, contradicting [L2]. Therefore $L$ is not context free.

Steps 1.1 and 2.1 show that $L$ satisfies the ordinary pumping condition, while step 2.2 shows that it is not context free. Thus [A1] is false.

In the displayed grammar, the production $S\to aSb$ has length three and mixes terminals with a variable, while $S\to ab$ has two terminals on the right-hand side. Neither production has one of the two forms listed in [L1].

Therefore the literal CYK recurrence does not know how to place $S$ into any table cell directly from those productions, so the proof of correctness in [L2] does not apply. One must first normalize the grammar as in [L3], or else modify the algorithm itself.

This contradicts [A1]. So CYK does require the normal-form preprocessing built into its proof.

Normalization preserves the language generated by a grammar, so it may be used as preprocessing for [L1], but it does not produce a canonical normal form whose literal equality settles language equality.

More decisively, [F1] states that the general CFG equivalence problem is undecidable. So no normalization-only method can decide it in full generality.

This contradicts [A1]. Therefore CFG equivalence is not decidable merely by normalization.