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 unam

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$.

Of course, this is only one argument, there might be completely different ones.

StackExchange Computer Science Q#33122, answer score: 4