This thesis investigates the relationship between the ambiguity functions for context-free grammars and for context-free languages. It also examines which functions are ambiguity functions and how different ambiguity classes relate to each other. The results can be applied to generalise known results on sequential and parallel parsing of context-free grammars.

To understand the main results we define some notions briefly:

The ambiguity of a word with respect to a context-free grammar is the number of its derivation trees. The ambiguity function of a context-free grammar maps an integer n to the maximal ambiguity of a word whose length is bounded by n. A context-free language L is f-ambiguous if f is the ambiguity function of some context-free grammar generating L and, roughly speaking, no context-free grammar generating L has a substantially lower ambiguity. A function is an inherent ambiguity function if there is an f-ambiguous context-free language. A homomorphism which maps a symbol either to itself or to the empty word is called a projection. A symbol a is called bounded in a language L if there is a constant c such that no word in L has more than c occurrences of the symbol a. A projection is a bounded contraction for a language L if it erases only symbols which are bounded in L.

The main results are:

1. The set of ambiguity functions for cycle-free context-free grammars and the set of inherent ambiguity functions coincide.

2. A technical statement which implies the following two facts:

2.1. The class of context-free languages with polynomially bounded ambiguity is the closure of the class of unambiguous context-free languages under bounded contractions.

2.2. Each reduced cycle-free context-free grammar G is either exponentially ambiguous or its ambiguity is bounded by a polynomial which can be computed from G. (2.2. was already part of the authors Diploma thesis, but the new proof yields in many cases a better polynomial (a polynomial with a lower degree), but never a worse polynomial.)

3. For each computable divergent total non-decreasing function f there is a divergent ambiguity function g such that g(n) is lower than or equal to f(n) for each positive integer n. In fact, the same ambiguity functions occur for the generation of rational trace languages over special independence alphabets. (A rational trace language T is generated by a regular (word) language R if T is the set of traces which are represented by the words in R. The ambiguity of a trace t is the number of representatives in R. It is now straightforward to define the ambiguity function for the generation of T by R.)

In addition the thesis contains generalisations for known results on sequential and parallel parsing of context-free grammars. In particular, the thesis considers the (sequential) Earley parsing time of context-free grammars with sublinear ambiguity functions (known to exist due to result 3). Moreover it is shown that each reduced context-free grammars with a polynomially bounded ambiguity can be parsed in logarithmic time on a CREW-PRAM. This is an immediate consequence of 2.1. and a known result for the parallel parsing time of unambiguous context-free grammars.