8
$\begingroup$

It is well known that testing whether a grammar is ambiguous is undecidable. It is however trivially decidable for any $G$ whether $L_n(G) := \{ w | w \in L(G) \wedge |w| \leq n \}$ for any $n \in \mathbb{N}$ contains any strings that have more than one derivation wrt $G$: just parse all these strings with some general parsing algorithm and check if any of them have more than one derivation. However, this approach has a running time of $\Omega(2^n)$.

Can we decide whether $L_n(G)$ contains any strings that have more than one derivation wrt $G$ in $poly(n)$?

The application of such a fast algorithm would be that one could run the algorithm on your grammar for a while, after which you can be fairly confident that your grammar is unambiguous: most grammars in practice, if they are ambiguous, have a relatively short string that exhibits this ambiguity, so one expects the algorithm to find it quickly.

I know that there has been quite a bit of work on ambiguity tests, but as far as I know most of these tests aim to approximate the ambiguity of a grammar (so it can misclassify grammars) rather than to exactly determine grammar ambiguity. The other approach I know of is fuzzers (test lots of random sentences on ambiguity).

The above question arose when I observed that a certain noncanonical LR algorithm could be used to solve the above problem as a side effect (though I have no idea what its running time would be if used for this purpose).

$\endgroup$
  • 1
    $\begingroup$ Would the technique I show here answer the question? $\endgroup$ – Raphael Apr 28 '12 at 10:08
  • $\begingroup$ @Raphael: I don't think it does: your method seems to be a general ambiguity test and I don't see how you can 'partially' apply it to test all strings up to some length for ambiguity. $\endgroup$ – Alex ten Brink Apr 28 '12 at 10:20
  • $\begingroup$ But you can: in general, it equality of generating functions is undecidable. Retrieving the first $n$ coefficients, on the other hands, is (afaik). So if you know the numbers of words up to size $n$, you can by the method I presented find the numbers of derivation trees up to size $n$. It won't work algorithmically if the grammar causes the equation system to have high degree, though. $\endgroup$ – Raphael Apr 28 '12 at 14:57
  • $\begingroup$ Do parsing algorithms check for parse trees of arbitrary height? For example, when checking if a string is ambiguous, how does one know there isn't a really long alternate derivation? $\endgroup$ – Kuhndog Feb 27 '15 at 22:15

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.