Quelltext der Seite Leerheitsproblem

Als '''Leerheitsproblem''' bezeichnet man in der [[Theoretische Informatik|theoretischen Informatik]] das Problem, zu entscheiden, ob eine in Form einer [[formale Grammatik|formalen Grammatik]] gegebene [[formale Sprache]] <math>L</math> leer ist, also <math>L = \empty</math>, oder nicht. Das Problem ist also, herauszufinden, ob es Wörter gibt, die den Regeln der Grammatik genügen, oder nicht.

Die [[Entscheidbarkeit]] des Leerheitsproblems hängt von der Komplexität der zugrundeliegenden Grammatik ab: Für die Grammatiken vom Typ 2 oder höher in der [[Chomsky-Hierarchie]] ist das Leerheitsproblem entscheidbar, für die Grammatiken bis Typ 1 im Allgemeinen jedoch nicht.

== Leerheitsproblem für endliche Automaten ==
Gegeben ist ein (nicht-)deterministischer [[endlicher Automat]] A. Es soll entschieden werden, ob die formale Sprache <math>L(A) = \empty</math> ist oder nicht.

Gesucht ist ein [[Algorithmus]] zur Lösung des Leerheitsproblems.

=== Naiver Ansatz ===
Man überprüft alle Wörter w (mit Länge ≤ Zustandsanzahl des Automaten), ob diese von A erkannt werden. Wird ein Wort erkannt, so gilt <math>L(A)</math> ≠ <math>\empty</math>, ansonsten ist die Sprache leer.

Der Ansatz ist für Alphabete mit mehr als einem Symbol und größere Automaten in der Praxis nicht einsetzbar – der Zeitbedarf ist exponentiell (<math>\mathcal{O}(2^n)</math>).

=== Markierungsalgorithmus ===
Der Markierungsalgorithmus betrachtet einen endlichen Automaten als gerichteten [[Graph (Graphentheorie)|Graphen]] G=(Q,E). Q-Elemente heißen Knoten und E-Elemente Kanten.
Wenn ein Wort w in L(A) existiert, gibt es einen Pfad vom Startzustand in den Endzustand des Automaten. Es wird nun überprüft, ob ein markierter Zustand des Graphen ein Endzustand des Automaten ist.

Beginnend vom Startzustand p1: p1 wird markiert und in die Liste der markierten Zustände aufgenommen. Dann wird überprüft, welche Zustände von p1 erreichbar sind. Markiere diese Zustände und füge p2, p3 … in die Liste ein und streiche p1 aus der Liste. Dies wird so lange wiederholt, bis alle zu erreichenden Zustände markiert sind und die Schlange leer ist. Ist kein Endzustand erreicht (und somit nicht markiert), gilt, dass die Sprache leer ist.

Der Algorithmus fügt jeden Knoten maximal einmal in die Liste hinzu und markiert ihn. Somit terminiert der Algorithmus im Zeitaufwand von n².

== Leerheitsproblem für Grammatiken ==
Bei dem Leerheitsproblem für eine Grammatik G ist die Frage, ob G eine leere Sprache erzeugt oder nicht.

Lösung über den Markierungsalgorithmus: Dabei werden die Symbole der Regeln markiert, aus denen ein Terminalwort ableitbar ist. Ist das Startsymbol markiert, dann ist die Sprache nicht leer.

== Siehe auch ==
* [[Äquivalenzproblem]]
* [[Endlichkeitsproblem]]
* [[Optimierungsproblem]]
* [[Wortproblem (Berechenbarkeitstheorie)|Wortproblem]]

[[Kategorie:Theorie formaler Sprachen]]