EXPONENTIAL AMBIGUITY OF CONTEXT-FREE GRAMMARS
Klaus Wich · Developments in Language Theory · 2000
A context-free grammar G is ambiguous if and only if there is a word that can be generated by G with at least two different derivation trees. Ambiguous grammars are often distinguished by their degree of ambiguity, which is the maximal number of derivation trees for the words generated by them. If there is no such upper bound G is said to be ambiguous of infinite degree. Here as a new tool for examining the ambiguity of cyclefree context-free grammars the ambiguity function is introduced. This function maps the natural number n to the maximal number of derivation trees which a word of length at most n may have. This provides the possibility to distinguish infinitely ambiguous context-free grammars by the growth-rate of their ambiguity functions. We present a necessary and sufficient, but in general undecidable, criterion for exponential ambiguity. In fact violation of this criterion leads to a polynomial upper bound for the ambiguity, which can be effectively constructed from the grammar. Hence for cycle-free context-free grammars the ambiguity function is either an element of 2 Θ(n) or of O(n d) for some d ∈ N0 which can be effectively constructed from G. 1