Ambiguity functions of context-free grammars and languages

Abstract

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.

In dieser Arbeit wird die Beziehung zwischen den Mehrdeutigkeitsfunktionen für kontextfreie Grammatiken und denen für kontextfreie Sprachen untersucht. Darüberhinaus wird untersucht, welche Funktionen Mehrdeutigkeitsfunktionen sind und wie verschiedene Mehrdeutigkeitsklassen miteinander zusammenhängen. Mit den Resultaten lassen sich bekannte Ergebnisse für sequenzielles und paralleles Parsing generalisieren. Zum Verständnis der Hauptresultate benötigen wir einige elementare Definitionen: Die Mehrdeutigkeit eines Wortes ist die Zahl seiner Ableitungsbäume. Die Mehrdeutigkeitsfunktion einer kontextfreien Grammatik bildet eine natürliche Zahl n auf die maximale Mehrdeutigkeit der Wörter ab, deren Länge durch n beschränkt ist. Eine kontextfreie Sprache L heißt f-deutig, wenn sie von einer kontextfreien Grammatik mit der Mehrdeutigkeitsfunktion f erzeugt wird und wenn, grob gesagt, keine kontextfreie Grammatik, welche L erzeugt, eine wesentlich langsamer wachsende Mehrdeutigkeitsfunktion hat. Eine Funktion f ist eine inhärente Mehrdeutigkeitsfunktion, wenn es eine f-deutige kontextfreie Sprache gibt. Ein Homomorphismus, welcher ein Symbol entweder auf sich selbst oder auf das leere Wort abbildet, heißt Projektion. Ein Symbol a ist beschränkt in einer Sprache L, wenn es eine Konstante c gibt, so dass kein Wort aus L mehr als c Vorkommen von a enthält. Eine Projektion ist eine beschränkte Kontraktion für eine Sprache L wenn sie nur beschränkte Symbole löscht. Die Hauptergebnisse sind: 1. Die Menge der Mehrdeutigkeitsfunktionen von zykelfreien kontextfreien Grammatiken und die Menge der inhärenten Mehrdeutigkeitsfunktionen fallen zusammen. 2. Eine technische Aussage mit den folgenden zwei Konsequenzen: 2.1. Die Klasse der Sprachen mit polynomiell beschränkter Mehrdeutigkeit ist der Abschluss der Klasse der eindeutig kontextfreien Sprachen unter beschränkten Kontraktionen. 2.2. Jede reduzierte zykelfreie kontextfreie Grammatik G ist entweder exponentiell mehrdeutig oder ihre Mehrdeutigkeit ist durch ein Polynom beschränkt, welches man aus G berechnen kann. (2.2. war bereits Teil der Diplomarbeit des Autors, allerdings liefert der neue Beweis oft ein besseres Polynom (niedrigerer Polynomgrad) aber niemals ein schlechteres.) 3. Für jede berechenbare divergente totale monoton nicht fallende Funktion f gibt es eine divergente Mehrdeutigkeitsfunktion g, so dass g(n) für alle natürlichen Zahlen n kleiner oder gleich f(n) ist. Tatsächlich erzielt man die gleichen Mehrdeutigkeitsfunktionen für rationale Spursprachen über bestimmten Unabhängigkeitsalphabeten. (Eine rationale Spursprache T wird von einer regulären (Wort-) Sprache R erzeugt, wenn T die Menge der durch die Wörter in R repräsentierten Spuren ist. Die Mehrdeutigkeit einer Spur t ist dabei die Anzahl der Repräsentanten von t in R. Dies führt in natürlicher Weise zu der Definition einer Mehrdeutigkeitsfunktion mit der R die Spursprache T erzeugt.) Zusätzlich enthält diese Arbeit Generalisierungen bekannter Resultate für das sequentielle und parallele Parsing von kontextfreien Grammatiken. Insbesondere wird die (sequentielle) Earleylaufzeit für kontextfreie Grammatiken mit sublinearer Mehrdeutigkeit (deren Existenz durch 3. bewiesen wurde) untersucht. Ferner wird gezeigt, dass logarithmische Zeit ausreicht, um reduzierte kontextfreie Grammatiken mit polynomiell beschränkter Mehrdeutigkeit auf einer CREW-PRAM zu parsen. Dies ergibt sich unmittelbar aus 2.1. und einem bekannten Resultat über die parallele Parsingzeit einer kontextfreien Grammatik.