Wortproblem (Berechenbarkeitstheorie)

Grundidee und Entscheidbarkeit

Das Wortproblem einer formalen Sprache ist in der Theoretischen Informatik das Entscheidungsproblem, ob ein gegebenes Wort zu dieser Sprache gehört oder nicht. Eine formale Sprache L besteht aus Wörtern über einem Alphabet; Σ* bezeichnet die Menge aller möglichen Wörter über diesem Alphabet.

Das Wortproblem einer Sprache L ist entscheidbar, wenn ihre charakteristische Funktion χ_L berechenbar ist. Diese Funktion ist definiert als χ_L: Σ* → {0,1}; für ein Wort w gilt χ_L(w) = 1, falls w ∈ L, und χ_L(w) = 0 sonst.

Anschaulich heißt das: L hat ein entscheidbares Wortproblem, wenn es einen Algorithmus gibt, der für jedes gegebene Wort w in endlicher Zeit feststellt, ob w zur Sprache L gehört oder nicht. Jedes Entscheidungsproblem kann als Wortproblem einer formalen Sprache codiert werden.

Wortproblem in der Chomsky-Hierarchie

Die Schwierigkeit des Wortproblems hängt davon ab, zu welcher Klasse die betrachtete Sprache gehört. Für die Chomsky-Hierarchie gelten folgende Aussagen:

• Für Typ-0-Sprachen ist das Wortproblem rekursiv aufzählbar, aber nicht entscheidbar. Das bedeutet: Zugehörigkeit kann grundsätzlich aufgezählt oder erkannt werden, aber es gibt keinen Algorithmus, der immer in endlicher Zeit für jedes Wort entscheidet.

• Für Typ-1-Sprachen ist das Wortproblem entscheidbar. Der Zeitbedarf ist höchstens exponentiell, die Platzkomplexität ist exakt linear. Daraus folgt auch, dass das Wortproblem für weiter eingeschränkte Sprachklassen entscheidbar ist.

• Für Typ-2-Sprachen ist das Wortproblem mit dem Cocke-Younger-Kasami-Algorithmus lösbar, wenn die Grammatik in Chomsky-Normalform vorliegt. Alternativ kann der Earley-Algorithmus verwendet werden, wenn eine Epsilon-freie Grammatik vorliegt. Der Zeitbedarf ist höchstens kubisch, die Platzkomplexität höchstens quadratisch.

• Für Typ-3-Sprachen ist das Wortproblem durch deterministische endliche Automaten lösbar. Die Zeitkomplexität ist linear, die Platzkomplexität konstant.