Verständnis

Question

Tut 3 Aufgabe 7:

 

Woher weiß ich denn, dass kontextfreie Sprachen in P liegen ?

 

Wie gehe ich denn da vor, auch für alle anderen Sprachen ?

 

Mfg

Answer 1

Es geht bei der Komplexität von Sprachen immer um das Wortproblem, also die Frage, ob ein Wort in der Sprache ist oder nicht. Man kann nun für kontextfreie Sprachen entweder über Grammatiken argumentieren oder über Kellerautomaten. Bei Grammatiken gibt es Algorithmen (bspw. den nicht mehr prüfungsrelevanten CYK-Parser), die für ein gegebenes Wort $w$ und eine gegebene kontextfreie Grammatik $G$ in Laufzeit $O(n^3)$ feststellen, ob $w \in L(G)$, und damit das Wortproblem lösen.

Auf der Automatenseite kann ein nichtdeterministischer Kellerautomat $K$ in Lienarzeit ausgeben, ob $w \in L(K)$. Das sagt zunächst noch nichts aus, denn Nichtdeterminismus ist in $P$ ja nicht erlaubt - aber man kann jeden nichtdeterministischen Kellerautomaten in Laufzeit $O(n^3)$ deterministisch simulieren.

Über beide Wege haben wir also einen deterministischen Pol-Zeit-Algorithmus, der das Wortproblem löst, und damit liegen (etwas salopp formuliert) "kontextfreie Sprachen in $P$". 

Typ-1-Sprachen sind $PSPACE$-vollständig, wie man über eine entsprechende Reduktion zeigen kann (das müssen Sie aber nicht können, merken Sie es sich einfach).

Typ-0-Sprachen sind nicht entscheidbar. Das wiederum sollte klar sein, da innerhalb der Typ-0-Sprachen auch solche schlimmen Probleme liegen wie das Halteproblem. Da das keine Turingmaschine entscheiden kann, wie wir aus der Vorlesung wissen, ist also das Wortproblem für Typ-0-Sprachen i.A. nicht entscheidbar.

Vielleicht können Sie nach diesen Hinweisen selber überlegen, welche Laufzeit das Wortproblem für Typ-3-Sprachen im schlimmsten Fall hat? (Am besten hier die Antwort posten!)

Viele Grüße

Lukas König

Comments

Naja Typ 3-Sprachen lassen sich ja mit EA abbilden, die entweder das Wort akzeptieren oder nicht. Hier spielt es keine Rolle, ob sie ndet EA oder det EA, da beide zueinander von der Spracherekennung äquivalent sind.

Was dies für einen Aufwand hat, weiß ich nicht, aber ich denke mal, max O(n^2), da ich ja immer nur entscheide, ob es ich in einem Endzustand bin oder nicht(linear O(n), aber Schleifen haben kann O(n*n).

Da reguläre Sprachen durch deterministisch EA erkennbar sind, würde ich diese zu der Komplexitätsklasse P zuordnen.

Stimmt das ?


Mfg

---

Es ist noch einfacher: Ein endlicher Automat (det. oder ndet.) arbeitet in jedem Schritt ein Zeichen der Eingabe ab, ist also für Eingaben der Länge $n$ nach genau $n$ Schritten fertig. Das ist alles.

---

Heißt das, dass er dann in keiner Problemklasse liegt ? :)
Wenn ja, sind dann nur die Probleme, die von det. TM gelöst werden können in P drin?
Aber eigentlich kann doch eine det. TM Typ 3 Sprachen auch erkennen, was wiederrum für L3 aus der Menge P sprechen würde..

LG

---

Jedes Problem liegt in einer Problemklasse - anders macht doch der Begriff überhaupt keinen Sinn!

Wenn ein endlicher Automat Linearzeit benötigt, dann kann er auch von einer det. TM in Linearzeit simuliert werden (das ist ja klar, eine TM ist ja ein EA mit mehr Features). Also liegt das Wortproblem für Typ-3-Sprachen natürlich in P.