Ψ Die Informatikseite

Menü
Informatik » Bachelor » Theoretische Informatik » Grammatiken » Wortproblem für Typ 0 und Typ 1 Sprachen
Kontextsensitive Sprachen - Typ 1 Grammatiken Reguläre Sprachen

Wortproblem für Typ 0 und Typ 1 Sprachen

Das Wortproblem für Sprachen vom Typ 0 ist unentscheidbar.

Dies ist im wesentlichen eine Folgerung aus der Unentscheidbarkeit des Halteproblems.

Das Wortproblem für Sprachen vom Typ 1 ist $PSPACE$-vollständig.

Wir können aufgrund dieser Erkenntnis ein Verfahren angeben, welchen Worstcaselaufzeit $EXPTIME$ hat.
Sei

\begin{displaymath}T_{n}^{0}=\{S\}\end{displaymath}

und

\begin{displaymath}T^{m+1}_{n}=T_{n}^{m}\cup\left\{x\in(V\cup\Sigma)^{*}:\vert x... ...n\wedge t\Rightarrow x\,f\uml {u}r\,ein\,t\in T_{n}^{m}\right\}\end{displaymath}

Wenn wir uns den Berechnungsbaum vorstellen, so ist $T_{n}^{m}$ die Menge der Wörter, die wir bis Ebene $m$ gebildet haben und die maximal die Länge $n$ haben.

Algorithmus zur Berechnung, ob ein Wort $w$ in der Sprache enthalten ist:
  • $n=\vert w\vert$
  • $m=0$
  • $T_{n}^{0}=\{S\}$
  • Wiederhole
    • Berechne $T_{n}^{m+1}$
    • $m=m+1$
  • Solange bis
    $\underbrace{w\in T_{n}^{m}}$ $\vee$ $\underbrace{T^{m+1}_{n}=T^{m}_{n}}$
    Wort enhalten   Es kommen keine neuen Wörter mehr hinzu $\rightarrow$ Wort nicht enhalten
Dieser Algorithmus hat exponentielle Laufzeit, da im schlimmsten Fall die Anzahl der Wörter in $T_{n}^{m}$ $\Theta(\vert V\vert\cup\vert\Sigma\vert)^{n}$ ist.
Kontextsensitive Sprachen - Typ 1 Grammatiken Reguläre Sprachen