Mit Google fortfahren
Wortproblem: Entscheidbarkeit einfach erklärt
Das Wortproblem fragt: Gehört ein gegebenes Wort $w$ zu einer formalen Sprache $L$? Ein Entscheidungsverfahren muss diese Frage für jedes Wort nach endlich vielen Schritten korrekt mit Ja oder Nein beantworten.
Auf dieser Seite lernst du, warum das je nach Sprachklasse unterschiedlich schwierig ist und weshalb das Wortproblem für Typ-1-Grammatiken durch eine endliche Suche entschieden werden kann.
Hake ab, was du schon kannst — und komm am Ende hierher zurück!
Aus einer Grammatik wird eine Ja-Nein-Frage
Eine formale Sprache ist eine Menge von Wörtern über einem Alphabet. Ist das Alphabet zum Beispiel $Σ = \{a,b\}$, dann sind a, abba und das leere Wort mögliche Wörter über diesem Alphabet.
Eine Grammatik $G$ erzeugt Wörter mithilfe von Produktionsregeln. Ihre Sprache wird mit $L(G)$ bezeichnet. Das Wortproblem für $G$ lautet daher:
$$w ∈ L(G)?$$
Die Eingabe besteht aus einem Wort – beim allgemeinen Wortproblem zusätzlich aus der Grammatik. Die Ausgabe ist Ja oder Nein.
Die Sprache $L = \{a^n b^n \mid n ≥ 0\}$ enthält gleich viele a wie b, wobei alle a vor den b stehen.
aabbgehört zu $L$, denn es hat die Form $a^2b^2$.ababgehört nicht zu $L$: Die Anzahl stimmt zwar, aber die Reihenfolge nicht.aabbbgehört nicht zu $L$, weil die Anzahlen verschieden sind.
Das Wortproblem verlangt einen Algorithmus, der diese Entscheidung für jedes Eingabewort trifft.
Entscheidbar und semi-entscheidbar sind nicht dasselbe
Entscheidbar
Eine Sprache ist entscheidbar, wenn ein Algorithmus für jede mögliche Eingabe nach endlich vielen Schritten hält und korrekt Ja oder Nein ausgibt.
Semi-entscheidbar
Eine Sprache ist semi-entscheidbar, wenn ein Verfahren jedes enthaltene Wort nach endlich vielen Schritten erkennt. Bei einem nicht enthaltenen Wort darf das Verfahren dagegen endlos weiterlaufen.
Eine Aufzählung aller erzeugbaren Wörter liefert deshalb nur eine „halbe“ Lösung: Taucht das gesuchte Wort auf, ist die Antwort Ja. Solange es nicht aufgetaucht ist, weißt du nicht, ob es später noch erscheint oder überhaupt nicht zur Sprache gehört.
Entscheidbar bedeutet: Ja- und Nein-Fälle enden immer. Semi-entscheidbar bedeutet: Nur für Ja-Fälle ist ein Ende garantiert.
Wähle in jeder Lücke die passende Form und prüfe anschließend deine Antworten.
Ein hält bei jeder Eingabe. Ein muss dagegen nur jedes enthaltene Wort nach endlich vielen Schritten erkennen. Läuft die Suche noch, ist die Zugehörigkeit daher .
Die Sprachklasse bestimmt das Verfahren
Die Chomsky-Hierarchie ordnet Grammatiken nach der Form ihrer Regeln. Für das Wortproblem ergibt sich folgendes Grundbild:
| Typ | Sprachklasse | Wortproblem |
|---|---|---|
| Typ 3 | regulär | entscheidbar, zum Beispiel mit einem endlichen Automaten |
| Typ 2 | kontextfrei | entscheidbar, zum Beispiel mit CYK nach Umformung in Chomsky-Normalform |
| Typ 1 | kontextsensitiv | entscheidbar durch eine endliche, längenbeschränkte Suche |
| Typ 0 | allgemein | im Allgemeinen nur semi-entscheidbar und nicht entscheidbar |
Beim CYK-Verfahren werden Teilwörter systematisch untersucht. Für ein Wort der Länge $n$ gibt es $n(n+1)/2$ relevante Tabellenzellen. Bei einer festen Grammatik benötigt das Verfahren höchstens eine Laufzeit der Größenordnung $O(n^3)$.
Die Typ-1-Suche ist ebenfalls ein Entscheidungsverfahren, kann aber exponentiell viele Satzformen untersuchen müssen. Entscheidbar bedeutet daher nicht automatisch praktisch schnell.
Die Mitgliedschaft eines einzelnen Wortes kann entscheidbar sein, obwohl andere Fragen über dieselbe Sprachklasse unentscheidbar sind. Für zwei kontextfreie Grammatiken ist etwa die Mitgliedschaft in ihrem Schnitt entscheidbar: Man prüft das Wort in beiden Sprachen. Ob der gesamte Schnitt leer ist, ist dagegen im Allgemeinen unentscheidbar.
Warum die Typ-1-Suche endlich ist
Typ-1-Grammatiken sind im Kern nicht verkürzend: Bei einer Regel $u → v$ gilt $|u| ≤ |v|$. Eine Satzform kann während einer Ableitung also nicht kürzer werden.
Gesucht sei ein Zielwort $w$ der Länge $n$. Würde eine Ableitung zwischendurch eine Satzform mit mehr als $n$ Zeichen erreichen, könnte sie später nicht wieder auf Länge $n$ schrumpfen. Dieser Zweig kann das Zielwort nicht mehr erzeugen und darf verworfen werden.
Über dem endlichen Alphabet aus Terminalen und Nichtterminalen gibt es nur endlich viele Satzformen mit höchstens $n$ Zeichen. Genau diese endliche Menge kann der Algorithmus durchsuchen.
Nicht verkürzende Regeln + feste Ziellänge = endlicher relevanter Suchraum.
Der Fixpunktalgorithmus arbeitet so:
- Setze $n = |w|$ und beginne mit der Menge $M = \{S\}$.
- Wende auf alle Formen in $M$ jede mögliche Regel an jeder passenden Stelle an.
- Füge nur neue Satzformen mit Länge höchstens $n$ zu $M$ hinzu.
- Ist $w$ enthalten, antworte Ja.
- Entstehen keine neuen Formen mehr, ist der Fixpunkt erreicht. Antworte dann Nein.
Der Algorithmus terminiert: Entweder findet er das Zielwort, oder die wachsende Menge kann nach endlich vielen Ergänzungen nicht mehr wachsen.
Eine Typ-1-Suche vollständig durchführen
Gegeben ist die Grammatik
$$G = (\{S,B\},\{a,b,c\},P,S)$$
mit den Regeln
- $S → aSBc$
- $S → abc$
- $cB → Bc$
- $bB → bb$
Zu prüfen ist das Wort aabbcc. Seine Länge beträgt $6$, daher werden nur Satzformen mit höchstens sechs Zeichen berücksichtigt.
Die erreichbaren Mengen wachsen schrittweise:
- $M_0 = \{S\}$
- $M_1 = \{S, aSBc, abc\}$
- $M_2 = M_1 ∪ \{aabcBc\}$
- $M_3 = M_2 ∪ \{aabBcc\}$
- $M_4 = M_3 ∪ \{aabbcc\}$
Der erfolgreiche Ableitungsweg lautet:
$$S ⇒ aSBc ⇒ aabcBc ⇒ aabBcc ⇒ aabbcc$$
Der Schritt $aSBc ⇒ aaSBcBc$ wird bei dieser Suche verworfen, weil die neue Satzform sieben Zeichen lang wäre. Sie kann wegen der nicht verkürzenden Regeln kein Zielwort der Länge sechs mehr ergeben.
Da aabbcc in $M_4$ liegt, lautet die Entscheidung Ja.
Wäre das Zielwort bis zum Fixpunkt nicht erschienen, dürfte der Algorithmus mit Nein enden. Genau dieses sichere Abbruchkriterium fehlt bei der bloßen Aufzählung einer allgemeinen Typ-0-Grammatik.
Typische Verwechslungen vermeiden
- Wortproblem oder Sprachvergleich? Das Wortproblem prüft ein einzelnes Wort. Es fragt nicht, ob zwei ganze Sprachen gleich sind.
- Nicht gefunden oder widerlegt? Bei einer unbegrenzten Aufzählung bedeutet „noch nicht gefunden“ nicht Nein. Erst ein begründeter endlicher Suchraum erlaubt diesen Schluss.
- Entscheidbar oder effizient? Ein Algorithmus kann sicher terminieren und dennoch exponentiell lange brauchen.
- Grammatiktyp oder konkretes Verfahren? Die Sprachklasse bestimmt, welche allgemeinen Verfahren und Garantien verfügbar sind.
- Leeres Wort: Bei Typ-1-Grammatiken gibt es unterschiedliche Konventionen. Manche Definitionen schließen verkürzende Regeln vollständig aus; andere erlauben unter einer Zusatzbedingung die Sonderregel $S → ε$. Der dargestellte Fixpunktalgorithmus behandelt nichtleere Zielwörter.
Karteikasten
Überlege zuerst selbst und drehe die Karte anschließend zum Prüfen um.
Alles auf einen Blick
- Wortproblem
- Eingabe: Wort und gegebenenfalls Grammatik
- Ausgabe: Ja oder Nein
- entscheidbar: Ende für jede Eingabe
- semi-entscheidbar: garantiertes Ende nur für Ja-Fälle
- Typ 3: endlicher Automat
- Typ 2: zum Beispiel CYK
- Typ 1: längenbeschränkte Fixpunktsuche
- Typ 0: im Allgemeinen unentscheidbar
Der entscheidende Zusammenhang lautet: Die Regeln einer Sprachklasse bestimmen, ob eine Suche begrenzt werden kann. Bei Typ 1 liefert die Nichtverkürzung eine Längengrenze und damit einen endlichen Suchraum. Bei Typ 0 fehlt eine solche allgemeine Grenze.
Abschluss-Check
Du beherrschst den Kern des Wortproblems, wenn du bei einer Lösung immer drei Fragen trennst: Was ist die Eingabe? Hält das Verfahren auch bei Nein? Welche Eigenschaft begrenzt die Suche?