Leerheitsproblem

Begriff und Entscheidbarkeit

Das Leerheitsproblem ist ein Entscheidungsproblem der theoretischen Informatik. Zu einer formal beschriebenen Sprache L soll festgestellt werden, ob sie leer ist, also ob L = ∅ gilt. Bei einer Grammatik bedeutet dies: Es wird geprüft, ob überhaupt mindestens ein Wort existiert, das sich nach ihren Regeln erzeugen lässt.

Die Entscheidbarkeit hängt von der Komplexität der Grammatik ab. Für Grammatiken vom Typ 2 oder höher in der Chomsky-Hierarchie ist das Leerheitsproblem entscheidbar; für Grammatiken bis Typ 1 ist es im Allgemeinen nicht entscheidbar.

Endliche Automaten

Bei einem deterministischen oder nichtdeterministischen endlichen Automaten A lautet die Frage, ob die von ihm erkannte Sprache L(A) leer ist. Eine Sprache ist genau dann nicht leer, wenn es mindestens ein Wort gibt, das den Automaten vom Startzustand zu einem Endzustand führt. Das Problem lässt sich deshalb als Erreichbarkeitsproblem in einem gerichteten Graphen auffassen.

Naive Wortsuche

Ein einfacher Ansatz prüft alle Wörter w, deren Länge höchstens der Zustandsanzahl des Automaten entspricht. Erkennt A mindestens eines dieser Wörter, gilt L(A) ≠ ∅. Wird keines erkannt, ist die Sprache leer.

Für Alphabete mit mehr als einem Symbol und größere Automaten ist dieses Verfahren praktisch ungeeignet, weil die Zahl der zu untersuchenden Wörter sehr schnell wächst. Der Zeitbedarf ist exponentiell und wird mit O(2^n) angegeben.

Markierung erreichbarer Zustände

Der Markierungsalgorithmus betrachtet den endlichen Automaten als gerichteten Graphen G = (Q, E). Die Elemente von Q sind die Zustände beziehungsweise Knoten, die Elemente von E die gerichteten Kanten beziehungsweise Übergänge. Existiert ein Wort w ∈ L(A), dann gibt es im Graphen einen Pfad vom Startzustand zu einem Endzustand.

Zunächst wird der Startzustand p1 markiert und in eine Liste aufgenommen. Danach bestimmt man alle von p1 aus erreichbaren, noch nicht markierten Zustände, markiert sie und fügt sie als p2, p3, … zur Liste hinzu. Der bereits bearbeitete Zustand p1 wird aus der Liste entfernt. Dieses Vorgehen wird für die weiteren Listeneinträge wiederholt, bis alle erreichbaren Zustände markiert sind und die als Schlange verwendete Liste leer ist.

Ist mindestens ein Endzustand markiert, ist L(A) nicht leer. Wurde kein Endzustand erreicht und markiert, gilt L(A) = ∅. Jeder Knoten wird höchstens einmal markiert und in die Liste eingefügt. Nach dem Artikel terminiert der Algorithmus daher mit einem Zeitaufwand von n².

Markierung bei Grammatiken

Für eine Grammatik G wird geprüft, ob sie mindestens ein Terminalwort erzeugt. Ein Terminalwort besteht vollständig aus Terminalsymbolen, also aus Zeichen, die im fertigen Wort vorkommen und nicht weiter ersetzt werden.

Auch hier kann ein Markierungsalgorithmus verwendet werden: Markiert werden die Symbole von Regeln, aus denen sich ein Terminalwort ableiten lässt. Wird auf diese Weise das Startsymbol der Grammatik markiert, ist die erzeugte Sprache nicht leer. Bleibt das Startsymbol unmarkiert, erzeugt G kein Terminalwort und ihre Sprache ist leer.