Wortproblem (Berechenbarkeitstheorie)

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 beide Begriffe sehr eng verwandt.

Das Wortproblem für Typ-3-Sprachen (= reguläre Sprachen, vgl. Chomsky-Hierarchie) ist entscheidbar. Die Komplexität ist linear.

Das Wortproblem für Typ-2-Sprachen (vgl. Chomsky-Hierarchie) ist entscheidbar. Effizient ist ist der CYK-Algorithmus (nach Cocke, Younger und Kasami), der Chomsky-Normalform voraussetzt.

Das Wortproblem für Typ-1-Sprachen (vgl. Chomsky-Hierarchie) ist entscheidbar, das heißt für eine formale Grammatik $G=\left(N,\Sigma ,P,S\right)\in Typ_{1}$ und $w\in \Sigma ^{*}$ gibt es einen Algorithmus, der in endlicher Zeit entscheidet, ob $w\in L\left(G\right)$ oder $w\notin L\left(G\right)$ . Die Komplexität ist exponenziell.

Für Typ-0-Sprachen ist das Wortproblem unentscheidbar!

Siehe auch