18
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Yes you are correct, a Turing machine cannot decide whether a context-free language is ambiguous or not, and this can be reduced from the post correspondence problem, which is undecidable. Note that a parse tree can be infinitely large, and we cannot decide when we stop the computation. $\endgroup$ – Hsien-Chih Chang 張顯之 Jan 17 '11 at 1:35
  • $\begingroup$ Hsien-Chih, are you referring to "parse trees" for words not in the language (i.e. unsuccessful parses), or are you trying to say that parse-trees can become arbitrarily large? $\endgroup$ – Raphael Jan 17 '11 at 8:31
21
$\begingroup$

We reduce from Post's Correspondence Problem. Suppose we can, in fact, decide the language $\{\langle G\rangle\vert G\textrm{ a CFG and }L(G)\textrm{ ambiguous}\}$.

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\}$, $R = \{S\rightarrow S_1\vert S_2, S_1\rightarrow \alpha_1 S_1 \sigma_1 \vert \cdots \vert \alpha_m S_1 \sigma_m \vert \alpha_1 \sigma_1 \vert \cdots \vert \alpha_m \sigma_m, S_2\rightarrow \beta_1 S_2 \sigma_1\vert \cdots \vert \beta_m S_2 \sigma_m \vert \beta_1 \sigma_1\vert \cdots \vert \beta_m \sigma_m\}$ (where $\sigma_i$ are new characters added to the alphabet, e.g., $\sigma_i = \underline{i}$).

If the language 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 to PCP, and since that's undecidable, we're done.

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

$\endgroup$
  • 1
    $\begingroup$ Try \textrm, like this: $\{\langle G\rangle \mid G \textrm{ a CFG and } L(G) \textrm{ ambiguous}\}$ $\endgroup$ – Hsien-Chih Chang 張顯之 Jan 17 '11 at 1:43

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.