Projekt A5 - Mehrdeutigkeit kontext-freier Sprachen und Grammatiken (Ambiguity of context-free languages and grammars)

(since 6/98, until 3/2000, continued in Stuttgart)

A context-free grammar G = (N,T,S,P) is unambiguous if for every word w in the language L(G) generated by G, there exists a unique derivation tree, otherwise, G is called ambiguous. If a language can only be generated by ambiguous context-free grammars, then this language is inherently ambiguous. Since there are context-free languages that are inherently ambiguous, we see that the ambiguous grammars contribute in an essential way to the expressive power of context-free grammars. Accordingly one is interested in investigating the quantitative aspects of ambiguity.

A grammar G is ambiguous of degree k for some integer k greater than 1, if for each word in the language L(G), there are at most k different derivation trees. If no such constant k exists for G, then the grammar G is called ambiguous of unbounded degree. For each integer k\(greater than 1), there exist grammars and languages that are ambiguous of degree k but not of degree k-1, and there exist grammars and languages that are ambiguous of unbounded degree.

The main concern of this project is an investigation of grammars and languages that are ambiguous of unbounded degree. By defining am_G(n) to denote the maximal degree of ambiguity for a word of length up to n that is generated by G, the ambiguity function am_G of the grammar G is obtained. This function can be used to classify the ambiguous grammars of unbounded degree. If it grows like a polynomial of degree n, then the grammar G is said to be polynomially ambiguous of degree n, and if this function grows exponentially, then the grammar G is exponentially ambiguous.


Klaus Wich


Wich, K.:
Exponential ambiguity of context-free grammars.
In Thomas, W., editor, DLT 99, Preproceedings, pages 87-100, Aachener Informatik-Berichte 99-5, RWTH Aachen, 1999.