<p>I have been trying to show the following language is undecidable.</p>

<p>$L = \{ (\langle G \rangle , n ): G$ is a context-free grammar with an ambiguous string of length $\le n \}$.</p>

<p>I think it is undecidable because if $G$ doesn't have an ambiguous string, it seems like one would have to check parse trees of arbitrary heights to verify they don't yield $s$.</p>

<p>Or, is there some lower bound on the height of a parse tree for a given string $s$, that is any derivation with more than some number of steps cannot yield $s$?  It seems like the presence of rules $S \to \varepsilon$, where $\varepsilon$ is the empty string, would ensure that there would exist parse trees of arbitrary height, in general.</p>

CC BY-SA 3.0
2015-02-28T05:18:54.083Z
Huh? Doesn't the CYK algorithm tell you in polynomial time whether any particular string is ambiguous for a given grammar? So just try it on all short strings.
David Eppstein
CC BY-SA 3.0
2015-02-28T07:50:59.810Z
CYK Assumes that the grammar is in Chomsky normal form, won't the conversion change the ambiguity?
Shaull
CC BY-SA 3.0
2015-03-01T00:15:02.423Z
It does not matter whether one uses CYK. Any derivation of a string of length n only involves strings of length at most n and can therefore be only of length (#variables+#terminals+1)^n. The algorithm therefore only needs to cycle through derivations of exponential length. Good enough for decidability.
Thomas S
CC BY-SA 3.0
2015-03-03T00:26:16.637Z
@Shaull As I remember CNF does not change ambiguity. Anyway, you do not need CNF to apply CYK, you only need to put the grammar in binary form, wich is a trivial transformation that barely changes the parse trees. It replaces n-ary nodes by an equivalent succession of n-1 binary ones.
babou
CC BY-SA 3.0
2015-03-03T00:29:53.100Z
@ThomasS You still may have to detect loops, which CYK does for you. To answer the OP, there is no upperbound on the height of a parse tree in general. Though people tend to avoid grammars that allow that. That is due to non-terminals that may derive into themselves. The empty string may help hide the phenomenon.
babou
CC BY-SA 3.0
2015-03-03T13:33:46.240Z
@babou: loop detection can be done by a counter: one only has to consider derivations using at most (#variables+#terminals+1)^n derivation steps. Well, maybe take this times 2, as loops can, of course, introduce the "desired" ambiguity.
Thomas S
CC BY-SA 3.0
2015-03-03T13:52:04.643Z
@ThomasS Well, whatever ... it is not hard. Using the counter assume the grammar contains no useless non terminals. I mean  we are fiddling with the obvious, myself included.
babou
<context-free><decidability>
Decidability of CFG ambiguity
Kuhndog
# Decidability of CFG ambiguity

(Asked by: username_0 on 2015-02-27)

I have been trying to show the following language is undecidable.

$L = \{ (\langle G \rangle , n ): G$ is a context-free grammar with an ambiguous string of length $\le n \}$.

I think it is undecidable because if $G$ doesn't have an ambiguous string, it seems like one would have to check parse trees of arbitrary heights to verify they don't yield $s$.

Or, is there some lower bound on the height of a parse tree for a given string $s$, that is any derivation with more than some number of steps cannot yield $s$? It seems like the presence of rules $S \to \varepsilon$, where $\varepsilon$ is the empty string, would ensure that there would exist parse trees of arbitrary height, in general.

**Tags:** context-free, decidability

> **Comments:**
> **username_1**: Huh? Doesn't the CYK algorithm tell you in polynomial time whether any particular string is ambiguous for a given grammar? So just try it on all short strings.  
> **username_2**: CYK Assumes that the grammar is in Chomsky normal form, won't the conversion change the ambiguity?  
> **username_3**: It does not matter whether one uses CYK. Any derivation of a string of length n only involves strings of length at most n and can therefore be only of length (#variables+#terminals+1)^n. The algorithm therefore only needs to cycle through derivations of exponential length. Good enough for decidability.  
> **username_4**: @username_2 As I remember CNF does not change ambiguity. Anyway, you do not need CNF to apply CYK, you only need to put the grammar in binary form, wich is a trivial transformation that barely changes the parse trees. It replaces n-ary nodes by an equivalent succession of n-1 binary ones.  
> **username_4**: @ThomasS You still may have to detect loops, which CYK does for you. To answer the OP, there is no upperbound on the height of a parse tree in general. Though people tend to avoid grammars that allow that. That is due to non-terminals that may derive into themselves. The empty string may help hide the phenomenon.  
> **username_3**: @username_4: loop detection can be done by a counter: one only has to consider derivations using at most (#variables+#terminals+1)^n derivation steps. Well, maybe take this times 2, as loops can, of course, introduce the "desired" ambiguity.  
> **username_4**: @ThomasS Well, whatever ... it is not hard. Using the counter assume the grammar contains no useless non terminals. I mean  we are fiddling with the obvious, myself included.  

---

## 0 answers

