„Wortproblem (Berechenbarkeitstheorie)“ – Versionsunterschied

Versionsgeschichte interaktiv durchsuchen

[ungesichtete Version]

← Zum vorherigen Versionsunterschied Zum nächsten Versionsunterschied →

Inhalt gelöscht Inhalt hinzugefügt

Inline

Version vom 28. Februar 2005, 04:06 Uhr

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 Komplexität ist linear.

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.

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

@@ Zeile 7: / Zeile 7: @@
 Das Wortproblem für Typ-1-Sprachen (vgl. [[Chomsky-Hierarchie]]) ist entscheidbar, das heißt für eine [[formale Grammatik]] <math>G = \left( N, \Sigma, P, S \right) \in Typ_1</math> und <math>w \in \Sigma^*</math> gibt es einen [[Algorithmus]], der in endlicher Zeit entscheidet, ob <math>w \in L \left( G \right)</math> oder <math>w \notin L \left( G \right)</math>. Die Komplexität ist exponenziell.
-Für Typ-0-Sprachen ist das Wortproblem unentscheidbar!
+Für Typ-0-Sprachen ist das Wortproblem unentscheidbar.
 ==Siehe auch==