# Decidability of CFG ambiguity

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.

• 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 Feb 28 '15 at 5:18
• CYK Assumes that the grammar is in Chomsky normal form, won't the conversion change the ambiguity? – Shaull Feb 28 '15 at 7:50
• 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 Mar 1 '15 at 0:15
• @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 Mar 3 '15 at 0:26
• @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 Mar 3 '15 at 0:29