Als Wortproblem einer formalen Sprache $L$ bezeichnet man in der Theoretischen Informatik das Entscheidungsproblem, zu einem gegebenen Wort zu entscheiden, ob dieses zur Sprache gehört oder nicht. Da sich umgekehrt jedes Entscheidungsproblem als Wortproblem einer formalen Sprache auffassen lässt, sind die beiden Begriffe sehr eng verwandt.

Das Wortproblem für Typ-3-Sprachen (= reguläre Sprachen, vgl. Chomsky-Hierarchie) ist entscheidbar. Die Zeitkomplexität des Problems ist linear, die Platzkomplexität ist konstant.

Das Wortproblem für Typ-2-Sprachen (vgl. Chomsky-Hierarchie) ist entscheidbar. Effizient ist der CYK-Algorithmus (nach Cocke, Younger und Kasami), der Chomsky-Normalform voraussetzt. Der Zeitbedarf ist höchstens kubisch, die Platzkomplexität ist höchstens der Logarithmus zum Quadrat.

Das Wortproblem für Typ-1-Sprachen (vgl. Chomsky-Hierarchie) ist entscheidbar, das heißt für eine formale Grammatik $G\; =\; \backslash left(\; N,\; \backslash Sigma,\; P,\; S\; \backslash right)\; \backslash in\; Typ\_1$ und $w\; \backslash in\; \backslash Sigma^*$ gibt es einen Algorithmus, der in endlicher Zeit entscheidet, ob $w\; \backslash in\; L\; \backslash left(\; G\; \backslash right)$ oder $w\; \backslash notin\; L\; \backslash left(\; G\; \backslash right)$ ist. Der Zeitbedarf ist höchstens exponentiell, die Platzkomplexität ist exakt linear.

Für Typ-0-Sprachen ist das Wortproblem rekursiv aufzählbar aber nicht entscheidbar.

Siehe auch

• Äquivalenzproblem
• Endlichkeitsproblem
• Leerheitsproblem
• Optimierungsproblem
• Suchproblem

Formale Sprachen | Rekursionstheorie | Komplexitätstheorie | Theoretische Informatik | Word problem (computability)