4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Raphael Nov 15 '14 at 8:28
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – David Smith Nov 15 '14 at 0:13
  • $\begingroup$ @David Intuitively, we expect it to be unambiguous because all longer words were unambiguous in the original grammar. $\endgroup$ – Yuval Filmus Nov 15 '14 at 3:17
  • $\begingroup$ 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? $\endgroup$ – David Smith Nov 15 '14 at 3:56
  • $\begingroup$ @David I'm saying that you can probably construct one from $G$. $\endgroup$ – Yuval Filmus Nov 15 '14 at 5:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.