Wortproblem

Als Wortproblem einer formalen Sprache bezeichnet man in der Theoretischen Informatik das Entscheidungsproblem, zu einem gegebenen Wort festzustellen, ob dieses zur Sprache gehört oder nicht. Das Wortproblem einer Sprache $L$ ist entscheidbar, wenn ihre charakteristische Funktion $\chi_L$ berechenbar ist. Sie ist definiert durch

$\chi_L\colon \Sigma^\ast \to \{0,1\};\ w \mapsto \begin{cases} 1, & \text{falls } w \in L \\ 0, & \text{sonst} \end{cases}$

Die Sprache $L$ hat also ein entscheidbares Wortproblem, wenn es einen Algorithmus gibt, der in endlicher Zeit herausfindet, ob $w \in L$ oder nicht. Jedes Entscheidungsproblem lässt sich als Wortproblem einer formalen Sprache codieren.

Die Schwierigkeit des Wortproblems hängt von der zugrunde gelegten Klasse der Sprachen ab. Für die Chomsky-Hierarchie ist bekannt:

• Das Wortproblem für Typ-0-Sprachen ist rekursiv aufzählbar und nicht entscheidbar.

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

• Das Wortproblem für Typ-2-Sprachen ist durch den Cocke-Younger-Kasami-Algorithmus lösbar, der die Chomsky-Normalform voraussetzt. Der Zeitbedarf ist höchstens kubisch, die Platzkomplexität ist höchstens quadratisch.

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

Siehe auch

• Äquivalenzproblem
• Endlichkeitsproblem
• Leerheitsproblem
• Optimierungsproblem
• Suchproblem