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?
$\begingroup$
$\endgroup$
2
-
3$\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, 2011 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$– RaphaelJan 17, 2011 at 8:31
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
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\}$, $$\begin{align} R = \{S_{\phantom0}&\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\} \end{align}$$ (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 from PCP, and since that's undecidable, we're done.
(Let me know if I've done anything boneheaded!)
-
1$\begingroup$ Try \textrm, like this: $\{\langle G\rangle \mid G \textrm{ a CFG and } L(G) \textrm{ ambiguous}\}$ $\endgroup$ Jan 17, 2011 at 1:43
-
$\begingroup$ I wonder if there is any another way to prove this without using PCP. Also what is the difference when we talk about an algorithm that tests ambiguity of an arbitrary CFG vs an algorithm that tests ambiguity of a particular CFG. $\endgroup$– rsonxAug 19, 2020 at 7:36
-
$\begingroup$ For anyone looking for the original source of this undecidability argument, I believe it is here: www-igm.univ-mlv.fr/~berstel/Mps/Travaux/A/… The reference is apparently: N.ChomskyM.P.Schützenberger, The Algebraic Theory of Context-Free Languages, Studies in Logic and the Foundations of Mathematics, volume 26, pages 118-161, 1959. Look for Ambiguity Theorem 2. $\endgroup$– a3nmDec 7, 2021 at 17:16
$\begingroup$
$\endgroup$
4
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 language is inherently ambiguous is a separate one. The undecidability of inherent ambiguity of a CFL was proved by Ginsburg and Ullian (JACM, January 1966). https://dl.acm.org/doi/10.1145/321312.321318
-
1$\begingroup$ This does not make much sense to me. A language is an infinite object, hence it cannot form an input to an algorithm in the first place. The question is only meaningful for languages given in some finite presentation. In fact, while not indicated very clearly, the Ginsburg and Ullian paper uses “language” as a shorthand for “context-free language” (this is stated in the Preliminaries), and they assume the languages are presented by grammars. Hence the result they actually prove is that it is undecidable whether a given context-free grammar generates an inherently ambiguous language. $\endgroup$ Apr 24, 2020 at 9:55
-
2$\begingroup$ @Emil the input is still a context free grammar but we ask if there exists a context free grammar that is unambiguous and language equivalent to the input grammar. $\endgroup$– FaustusApr 24, 2020 at 14:38
-
2$\begingroup$ @Faustus That’s exactly what I’m saying: we ask if a given context-free grammar (not language) generates an inherently unambiguous language. $\endgroup$ Apr 24, 2020 at 15:59
-
$\begingroup$ @Emil: since the usual representations of context-free languages can be easily transformed into each other (grammars, PDAs, you name it), it makes perfect sense to say that the question at hand is undecidable for context-free languages. Especially, in an informal description. $\endgroup$– Thomas SMay 16 at 19:46