2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.