Leerheitsproblem

Als Leerheitsproblem bezeichnet man in der theoretischen Informatik das Problem, zu entscheiden, ob eine in Form einer formalen Grammatik gegebene formale Sprache $L$ leer ist, also $L=\emptyset$ , 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 $L(A)=\emptyset$ 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 $L(A)$ ≠ $\emptyset$ , 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 ( ${\mathcal {O}}(2^{n})$ ).

Markierungsalgorithmus

Der Markierungsalgorithmus betrachtet einen endlichen Automaten als gerichteten 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².