Wortproblem
aus Wikipedia, der freien Enzyklopädie
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 quadratisch.
Das Wortproblem für Typ-1-Sprachen (vgl. Chomsky-Hierarchie) ist entscheidbar, das heißt für eine formale Grammatik 
und 
gibt es einen Algorithmus, der in endlicher Zeit entscheidet, ob 
oder 
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 im Allgemeinen nicht entscheidbar.
