<p>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)$.</p>

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

<p>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.</p>

<p>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).</p>

<p>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).</p>

CC BY-SA 3.0
2012-04-28T10:08:47.723Z
Would the technique I show [here](http://math.stackexchange.com/questions/22463/is-this-bnf-grammar-ambiguous/22467#22467) answer the question?
Raphael
CC BY-SA 3.0
2012-04-28T10:20:54.113Z
@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.
Alex ten Brink
CC BY-SA 3.0
2012-04-28T14:57:04.037Z
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.
Raphael
CC BY-SA 3.0
2015-02-27T22:15:28.050Z
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?
Kuhndog
<fl.formal-languages><time-complexity><context-free>
Is there an ambiguity test for CFGs faster than trying all strings?
Alex ten Brink
# Is there an ambiguity test for CFGs faster than trying all strings?

(Asked by: username_0 on 2012-04-28)

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).

**Tags:** fl.formal-languages, time-complexity, context-free
> **Comments:**
> **username_1**: Would the technique I show [here](http://math.stackexchange.com/questions/22463/is-this-bnf-grammar-ambiguous/22467#22467) answer the question?  
> **username_0**: @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.  
> **username_1**: 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.  
> **username_2**: 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?  

---

## 0 answers

