Leerheitsproblem - LinkFang.de





Leerheitsproblem


Als Leerheitsproblem bezeichnet man in der Theoretischen Informatik das Problem, zu entscheiden, ob eine in Form einer formalen Grammatik gegebene formale Sprache [math]L[/math] leer ist, also [math]L = \empty[/math], oder nicht. Das Problem ist es 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 Automatens), 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 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 solange 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


Kategorien: Theorie formaler Sprachen

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Leerheitsproblem (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.