<p>The answer by <a href="https://cstheory.stackexchange.com/users/3169/alpoge">apolge</a> 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 <strong>inherently ambiguous</strong> language is a separate one. The undecidability of inherent ambiguity of a CFG was proved by Ginsburg and Ullian (JACM, January 1966). <a href="https://dl.acm.org/doi/10.1145/321312.321318" rel="nofollow noreferrer">https://dl.acm.org/doi/10.1145/321312.321318</a></p>

CC BY-SA 4.0
2020-04-24T09:55:56.920Z
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*.
Emil Jeřábek
CC BY-SA 4.0
2020-04-24T14:38:24.077Z
@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.
Faustus
CC BY-SA 4.0
2020-04-24T15:59:52.860Z
@Faustus That’s exactly what I’m saying: we ask if a given context-free *grammar* (not language) generates an *inherently unambiguous* language.
Emil Jeřábek
CC BY-SA 4.0
2023-05-16T19:46:28.587Z
@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.
Thomas S
CC BY-SA 4.0
2023-12-11T08:28:03.807Z
@ThomasS In another context, this could work. But not here, as the problem is explicitly contrasted with alpoge's answer. The answer here falsely and misleadingly suggests, with emphasis, that the two problems take input of a different kind (a CFG in alpoge's answer, and some direct input of a CFL here, whatever it might mean). In fact, the inputs of both problems are *identical*.
Emil Jeřábek
CC BY-SA 4.0
2020-02-18T08:46:57.050Z
2023-12-11T12:48:33.593Z
2023-12-11T12:48:33.593Z
Michael Burke
<p>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 &quot;finite&quot; 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).</p>
<p>In my opinion, then, the ambiguitiy is on the grammar, and not on the language. That is why they use the term &quot;inherently&quot; ambiguous; to refer to the CFG but not the language. Indeed the CFG refers to the CFL, whose definition is tied to the CFG.</p>
<p>But in the end, we are proving that the grammar is ambiguous, not the language.</p>
<p>I am wondering if I am missing something here.</p>

CC BY-SA 4.0
2023-12-10T21:25:04.537Z
There context-free languages for which no unambiguous
 context-free grammar exist. Such languages are called
 *inherently ambiguous*. According to [Wikipedia](https://en.wikipedia.org/wiki/Ambiguous_grammar#Inherently_ambiguous_languages)
 the union of $\{a^{n}b^{n}c^{m}d^{m}\mid n,m>0\}$ with
 $\{a^{n}b^{m}c^{m}d^{n}\mid n,m>0\}$ is context-free and inherently ambiguous.
Martin Berger
CC BY-SA 4.0
2023-12-10T16:03:48.403Z
2023-12-10T16:06:54.513Z
2023-12-10T16:06:54.513Z
Luis R
<p>We reduce from <a href="https://en.wikipedia.org/wiki/Post_correspondence_problem" rel="nofollow noreferrer">Post's Correspondence Problem</a>. Suppose we can, in fact, decide the language <span class="math-container">$\{\langle G\rangle\mid G\textrm{ is an ambiguous CFG}\}$</span>.</p>
<p>Given <span class="math-container">$\alpha_1, \ldots, \alpha_m, \beta_1, \ldots, \beta_m$</span>:
Construct the following CFG <span class="math-container">$G = (V,\Sigma,R,S)$</span>:
<span class="math-container">$V = \{S, S_1, S_2\}$</span>,
<span class="math-container">$$\begin{align}
R = \{S_{\phantom0}&amp;\rightarrow S_1\mid S_2,\\
S_1&amp;\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&amp;\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}$$</span>
(where <span class="math-container">$\sigma_i$</span> are new characters added to the alphabet, e.g., <span class="math-container">$\sigma_i = \underline{i}$</span>).</p>
<p>If the grammar is ambiguous, then there is a derivation of some string <span class="math-container">$w$</span> in two different ways. Supposing, wlog, that the derivations both start with the rule <span class="math-container">$S\rightarrow S_1$</span>, 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 <span class="math-container">$S_1$</span> and one <span class="math-container">$S_2$</span> 'start'. But then, taking the substring of <span class="math-container">$w$</span> 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).</p>
<p>Similarly, if there is no ambiguity, then the PCP cannot be solved, since a solution would imply an ambiguity that just follows <span class="math-container">$S\Rightarrow S_1\Rightarrow^* \alpha\tilde{\sigma}$</span> and <span class="math-container">$S\Rightarrow S_2\Rightarrow^* \beta\tilde{\sigma}$</span>, where <span class="math-container">$\alpha = \beta$</span> are strings of matching <span class="math-container">$\alpha$</span>'s and <span class="math-container">$\beta$</span>'s (since the <span class="math-container">$\tilde{\sigma}$</span>'s match).</p>
<p>Hence, we've reduced from PCP, and since that's undecidable, we're done.</p>
<p>(Let me know if I've done anything boneheaded!)</p>

CC BY-SA 4.0
2020-08-19T07:36:51.593Z
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.
rsonx
CC BY-SA 4.0
2021-12-07T17:16:42.817Z
For anyone looking for the original source of this undecidability argument, I believe it is here: http://www-igm.univ-mlv.fr/~berstel/Mps/Travaux/A/1963-7ChomskyAlgebraic.pdf 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.
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2011-01-17T01:39:01.810Z
2023-12-11T12:51:37.293Z
2023-12-11T12:51:37.293Z
alpoge
<p>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? </p>

CC BY-SA 2.5
2011-01-17T01:35:02.967Z
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.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-01-17T08:31:46.057Z
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?
Raphael
<computability><turing-machines><context-free><ambiguity>
How is proving a context free language to be ambiguous undecidable?
Ulkmun
# How is proving a context free language to be ambiguous undecidable?

(Asked by: username_0 on 2011-01-17)

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?

**Tags:** computability, turing-machines, context-free, ambiguity
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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?  

---

## 3 answers

### Answer by username_9 on 2011-01-17. Score: 33 | Accepted answer

We reduce from [Post's Correspondence Problem](https://en.wikipedia.org/wiki/Post_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!)

> **Comments:**
> **username_10**: 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.  
> **username_11**: For anyone looking for the original source of this undecidability argument, I believe it is here: http://www-igm.univ-mlv.fr/~berstel/Mps/Travaux/A/1963-7ChomskyAlgebraic.pdf 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.  

---

### Answer by username_3 on 2020-02-18. Score: 13

The answer by [apolge](https://cstheory.stackexchange.com/users/3169/alpoge) 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>

> **Comments:**
> **username_4**: 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*.  
> **username_5**: @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.  
> **username_4**: @Faustus That’s exactly what I’m saying: we ask if a given context-free *grammar* (not language) generates an *inherently unambiguous* language.  
> **username_6**: @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.  
> **username_4**: @ThomasS In another context, this could work. But not here, as the problem is explicitly contrasted with alpoge's answer. The answer here falsely and misleadingly suggests, with emphasis, that the two problems take input of a different kind (a CFG in alpoge's answer, and some direct input of a CFL here, whatever it might mean). In fact, the inputs of both problems are *identical*.  

---

### Answer by username_7 on 2023-12-10. Score: -4

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.

> **Comments:**
> **username_8**: There context-free languages for which no unambiguous  context-free grammar exist. Such languages are called  *inherently ambiguous*. According to [Wikipedia](https://en.wikipedia.org/wiki/Ambiguous_grammar#Inherently_ambiguous_languages)  the union of $\{a^{n}b^{n}c^{m}d^{m}\mid n,m>0\}$ with  $\{a^{n}b^{m}c^{m}d^{n}\mid n,m>0\}$ is context-free and inherently ambiguous.  

---

