# Show that every grammar for an inherently ambiguous CFL has infinitely many ambiguities

Prove that if a CFL $L$ is inherently ambiguous, then for any grammar $G$ with $L(G) = L$, there are infinitely many strings in $L$ that have (at least) 2 different derivations in $G$.

Here's a sketch of a proof I have in mind:

Suppose $G = (V, \Sigma, P, S)$ is a grammar satisfying $L(G) = L$. Then, since $L$ is inherently ambiguous, it must be that $G$ is ambiguous. Hence, there exists a string, call it $z$, with two different derivations in $G$. Now, if the right-hand side of every production in G is of length $\leq d$, and if $|z| \geq d^{|V| + 1}$, then by Ogden's Lemma, if $d^{|V| + 1}$ or more symbols of $z$ are marked arbitrarily, there exists a decomposition $z = uvwxy$ such that there exists a variable $A$ in G such that

$S \Longrightarrow^* uAy$

$A \Longrightarrow^* vAx$

$A \Longrightarrow^* w$

Hence, every derivation of $z$ must at least contain the sentential forms $S \Longrightarrow^* uAy \Longrightarrow^* uvAxy \Longrightarrow^* uvwxy = z$

In particular, we may indefinitely "pump" the sentential form $uvAxy$ in both derivations via repeated application of $A \Longrightarrow^* vAx$. Hence, the resulting two derivations must at least contain the sentential forms

$S \Longrightarrow^* uAy \Longrightarrow^* uvAxy \Longrightarrow^* uv^iAx^iy \Longrightarrow^* uv^iwx^iy \in L$

Both derivations; however, are still different, and thus we have that strings of the form $uv^iwx^iy \in L$, with $i \geq 2$ have 2 distinct derivations. Hence, there are infinitely many strings in $L$ with 2 different derivations.

Now, I do see some problems with this sketch. For one, we cannot guarantee that $|z| \geq d^{|V| + 1}$. Second, even if $|z| \geq d^{|V| + 1}$, I'm not sure that we can guarantee that both derivations of z must contain the sentential forms $S \Longrightarrow^* uAy \Longrightarrow^* uvAxy \Longrightarrow^* uvwxy = z$.

Given $k = |V|$, suppose that every string of length $\geq d^{k+1}$ is unambiguous in G. Let $z$ be an arbitrary string in $L$, with $|z| \geq d^{k+1}$. Then by Ogden's lemma, there exists a decomposition $z = uvwxy$ and a derivation of $uv^2wx^2y$, namely:

$S \Longrightarrow^* uAy \Longrightarrow^* uvAxy \Longrightarrow^* uv^2Ax^2y \Longrightarrow^* uv^2wx^2y$. Clearly, $|uv^2wx^2y| \geq d^{|V| + 1}$, and thus the provided derivation for the string is unique. But now, mark only the characters in $uv^2wx^2y$ which appear in $u, w, \text{ or } y$. The resulting derivation for $uv^2wx^2y$, obtained using Ogden's Lemma, must differ from the previous derivation for $uv^2wx^2y$, contradiction. Hence, there exists an ambiguous string of length $\geq d^{|V| + 1}$, and we may apply the argument above.

• FWIW, while Yuval's approach is conceptually simpler, I think a pumping argument should work. All you need is $L \ni w = \dots xyz\dots$ s.t. there are two distinct left-derivations with $A \Rightarrow^* xAz \Rightarrow^* xyz$ -- then, pumping gives you infinitely many ambiguous words. – Raphael Nov 15 '14 at 8:28

Intuitively, the reason the claim is true is that if a grammar $G$ had only finitely many ambiguous strings, then you could somehow resolve the ambiguity and come up with an equivalent unambiguous grammar $G'$, thus contradicting the inherent ambiguity. The way you would resolve the ambiguity is something like this: you would generate all small strings (say at most $\ell$, the length of the maximal ambiguous word in $G$) explicitly (and unambiguously), and modify the grammar so that all other strings that it generates are longer; for example, you could have a different subgrammar for every prefix of length $\ell+1$ which simulates $G$.
• I understand how, in the new grammar you've proposed, we could have explicit rules of the form $S \longrightarrow w$, where $w$ is a string in $L$ of length $\leq l$, but how do we ensure that the remainder of the new grammar (i.e., the part of the grammar which generates strings in $L$ of length $> l$) is unambiguous? – David Smith Nov 15 '14 at 0:13
• So what you are saying is that because the original grammar $G$ is unambiguous for all the strings it generates that are of length $l + 1$ or greater, there must exist a unambiguous grammar, say $G_1$, whose language is all the strings in $L$ of length $l + 1$ or greater? – David Smith Nov 15 '14 at 3:56
• @David I'm saying that you can probably construct one from $G$. – Yuval Filmus Nov 15 '14 at 5:56