wilhelm büchner_728x90_bachelor_informatik
  Home     
    
    Bücher   Links   Impressum

next up previous contents
Nächste Seite: Reguläre Sprachen Aufwärts: Grammatiken Vorherige Seite: Kontextsensitive Sprachen - Typ   Inhalt

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.
next up previous contents
Nächste Seite: Reguläre Sprachen Aufwärts: Grammatiken Vorherige Seite: Kontextsensitive Sprachen - Typ   Inhalt