[Solved]: Show that every grammar for an inherently ambiguous CFL has infinitely many ambiguities

Problem Detail: 

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.

Asked By : David Smith

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33122

 Ask a Question

 Download Related Notes/Documents