How is proving a context free language to be ambiguous undecidable?

Question

I've read somewhere that a Turing machine cannot compute this and it's therefore undecidable but why? Why is it computationally impossible for a machine to generate the parse tree's and make a decision? Perhaps I'm wrong and it can be done?

Answer 1

We reduce from Post's Correspondence Problem. Suppose we can, in fact, decide the language $\{\langle G\rangle\mid G\textrm{ is an ambiguous CFG}\}$.

Given $\alpha_1, \ldots, \alpha_m, \beta_1, \ldots, \beta_m$: Construct the following CFG $G = (V,\Sigma,R,S)$: $V = \{S, S_1, S_2\}$, $$\begin{align} R = \{S_{\phantom0}&\rightarrow S_1\mid S_2,\\ S_1&\rightarrow \alpha_1 S_1 \sigma_1 \mid \cdots \mid \alpha_m S_1 \sigma_m \mid \alpha_1 \sigma_1 \mid \cdots \mid \alpha_m \sigma_m,\\ S_2&\rightarrow \beta_1 S_2 \sigma_1\mid \cdots \mid \beta_m S_2 \sigma_m \mid \beta_1 \sigma_1\mid \cdots \mid \beta_m \sigma_m\} \end{align}$$ (where $\sigma_i$ are new characters added to the alphabet, e.g., $\sigma_i = \underline{i}$).

If the grammar is ambiguous, then there is a derivation of some string $w$ in two different ways. Supposing, wlog, that the derivations both start with the rule $S\rightarrow S_1$, reading the new characters backwards until they end makes sure there can only be one derivation, so that's not possible. Hence, we see that the only ambiguity can come from one $S_1$ and one $S_2$ 'start'. But then, taking the substring of $w$ up to the beginning of the new characters, we have a solution to the PCP (since the strings of indices used after those points match).

Similarly, if there is no ambiguity, then the PCP cannot be solved, since a solution would imply an ambiguity that just follows $S\Rightarrow S_1\Rightarrow^* \alpha\tilde{\sigma}$ and $S\Rightarrow S_2\Rightarrow^* \beta\tilde{\sigma}$, where $\alpha = \beta$ are strings of matching $\alpha$'s and $\beta$'s (since the $\tilde{\sigma}$'s match).

Hence, we've reduced from PCP, and since that's undecidable, we're done.

(Let me know if I've done anything boneheaded!)

Answer 2

The answer by apolge presents the proof that it is undecidable whether an arbitrary context free grammar is ambiguous. The question of whether a context free grammar defines an inherently ambiguous language is a separate one. The undecidability of inherent ambiguity of a CFG was proved by Ginsburg and Ullian (JACM, January 1966). https://dl.acm.org/doi/10.1145/321312.321318

Answer 3

A language is a set of strings drawn from an alphabet. Then, paradoxically, the language per se, should be defined unambiguously by enumerating all strings of it. This is true and can be proved for a finite language. But for infinite languages, it is impossible to give an explicit representation of it. Thus, a "finite" way of describing (defining or representing the language) should be used. English prose (or say, natural language) is amgibuous. Now, in case of a CFL, we use a grammar to define it (or eventually the equivalent, the PDA), and that grammar is context free (CFG).

In my opinion, then, the ambiguitiy is on the grammar, and not on the language. That is why they use the term "inherently" ambiguous; to refer to the CFG but not the language. Indeed the CFG refers to the CFL, whose definition is tied to the CFG.

But in the end, we are proving that the grammar is ambiguous, not the language.

I am wondering if I am missing something here.