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

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