Wortproblem: Entscheidbarkeit einfach erklärt

Beim Wortproblem sind eine formale Sprache und ein Wort gegeben. Die Frage lautet: Gehört dieses Wort zu dieser Sprache? Die Antwort ist Ja oder Nein. Die Sprache muss dafür eindeutig beschrieben sein, etwa durch eine vollständige Wortliste oder durch Regeln.

Ein Alphabet ist eine endliche Menge erlaubter Zeichen. Dass ein Wort aus erlaubten Zeichen besteht, reicht für die Zugehörigkeit zur Sprache nicht aus. Auch die Reihenfolge der Zeichen und die Regeln der Sprache zählen. Das Wortproblem fragt weder nach der Wortlänge noch nach einer Bedeutung im Deutschen.

Ein Algorithmus ist ein eindeutig beschriebenes Verfahren mit ausführbaren Schritten. Eine Sprache heißt entscheidbar, wenn es einen Algorithmus gibt, der für jedes Eingabewort nach endlich vielen Schritten die richtige Antwort Ja oder Nein liefert. Ein solches Verfahren heißt Entscheider.

Eine Sprache heißt semi-entscheidbar, wenn es einen Algorithmus gibt, der jedes zugehörige Wort nach endlich vielen Schritten mit Ja erkennt. Für Wörter außerhalb der Sprache ist keine beendete Nein-Antwort garantiert: Das Verfahren darf dort unbegrenzt weiterlaufen. Eine falsche Ja-Antwort ist nicht erlaubt.

Jede entscheidbare Sprache ist auch semi-entscheidbar: Ihr Entscheider erkennt insbesondere die Ja-Fälle. Der umgekehrte Schluss gilt nicht allgemein. Es gibt semi-entscheidbare Sprachen ohne Entscheider; sie heißen unentscheidbar. Dass ein bestimmtes Verfahren bei manchen Eingaben endlos läuft, beweist aber noch keine Unentscheidbarkeit. Ein anderes Verfahren könnte die Sprache entscheiden.

Eine formale Grammatik beschreibt eine Sprache durch endlich viele Ersetzungsregeln. Diese erzeugen Wörter aus einem Startsymbol, also einem festgelegten Anfangszeichen. Die Chomsky-Hierarchie ist eine Einteilung formaler Sprachen nach den erlaubten Formen solcher Regeln. Sie unterscheidet die Typen 0, 1, 2 und 3.

Die Sprachklassen sind ineinander enthalten: Jede Typ-3-Sprache ist auch eine Typ-2-Sprache, jede Typ-2-Sprache auch eine Typ-1-Sprache und jede Typ-1-Sprache auch eine Typ-0-Sprache. Für Typ 1, Typ 2 und Typ 3 ist das Wortproblem entscheidbar.

Für jede Typ-0-Sprache ist das Wortproblem semi-entscheidbar. Unter den Typ-0-Sprachen gibt es aber auch Sprachen mit unentscheidbarem Wortproblem. Die Aussage „Typ 0 ist im Allgemeinen nicht entscheidbar“ bedeutet deshalb nicht, dass jede einzelne Typ-0-Sprache unentscheidbar ist. Der Typ 0 allein garantiert weder Entscheidbarkeit noch Unentscheidbarkeit.

Terminalsymbole sind die Zeichen fertiger Wörter. Nichtterminalsymbole sind Platzhalter, die durch Regeln ersetzt werden. Eine Herleitung ist eine Folge solcher Regelanwendungen. Jede dabei entstehende Zeichenfolge heißt Satzform; sie kann noch Platzhalter enthalten. Ihre Länge zählt jedes Symbol, auch jeden Platzhalter. Das endliche Vokabular einer Grammatik besteht aus ihren Terminalsymbolen und Nichtterminalsymbolen. Der Pfeil \to in einer Regel bedeutet „ersetze durch“.

Wir verwenden hier die Typ-1-Konvention, bei der das Startsymbol S auf keiner rechten Regelseite vorkommt. Die Regeln verkürzen Satzformen nicht. Als Ausnahme darf die Regel S \to \varepsilon vorkommen. Dabei bezeichnet \varepsilon das leere Wort, also das Wort mit null Zeichen. Für ein leeres Zielwort prüfst du gesondert: Ist diese Ausnahmeregel vorhanden, lautet die Antwort Ja; andernfalls Nein.

Für ein nichtleeres Zielwort bezeichne n seine Zeichenanzahl. Beginne mit der Satzform S. Speichere sie als besucht und in einer Liste der noch zu untersuchenden Satzformen. Nimm jeweils eine Satzform aus dieser Liste. Ist sie genau das Zielwort, antworte Ja. Andernfalls wende jede passende Regel an jeder passenden Stelle an. Berücksichtige dabei alle entstehenden Satzformen bis zur Länge n. Eine noch nicht besuchte Satzform speicherst du als besucht und nimmst sie in die Liste auf. Bereits besuchte Satzformen untersuchst du nicht erneut. Die Ausnahmeregel für das leere Wort lässt du bei dieser Suche weg: Das Startsymbol kann nicht später wieder auftreten, und das leere Wort hilft nicht beim Erzeugen eines nichtleeren Zielworts.

Längere Satzformen kannst du ausschließen, weil sie nicht mehr auf die Zielwortlänge schrumpfen können. Über dem endlichen Vokabular gibt es nur endlich viele Satzformen der Längen eins bis n. Jede wird höchstens einmal zur Untersuchung aufgenommen. Auch ein Kreis von längenerhaltenden Regeln kann die Suche deshalb nicht endlos machen. Eine bekannte Satzform hat dieselben möglichen Fortsetzungen, unabhängig davon, auf welchem Weg du sie erreicht hast. Ist die Liste leer, ohne dass das Zielwort gefunden wurde, antworte Nein.