Widerspruch in Übung 8, Aufgabe 6?

[robert.n]

Hallo,

in Aufgabe 6 von Übung 8 (E8.6) heißt es in der Musterlösung zu a), dass jede kontextfreie Sprache entscheidbar ist und dass alle entscheidbaren Sprachen unter Komplement abgeschlossen sind.
In b) heißt es dann aber, dass die kontextfreien Sprachen nicht unter Komplement abgeschlossen sind.

Wie kann ich mir das erklären? Wäre sehr dankbar, wenn mir das noch jemand vor morgen klarmachen könnte.

// EDIT: Ich glaube es hat sich gerade erledigt. Wenn ich das richtig verstanden habe, dann hat zwar jede kontextfreie Sprache ein aufzählbares Komplement, aber dieses Komplement ist im Allgemeinen nicht selbst kontextfrei. Die gemeinte "Abgeschlossenheit" in a) bedeutet dann wohl so viel wie: "Das Komplement ist auch entscheidbar". Oder?!

MfG, Robert

[linn]

jo verstehe ich genauso.
"Die Entscheidbaren sprachen sind unter komplement abgeschlossen" heisst soviel wie: das komplement einer entscheidbaren sprache ist auch eine entscheidbare sprache (muss aber nicht vom selben typ in der chomsky hierarchie sein)

Gibt es eigentlich irgendne Zusammenfassung für den ganzen Kram der bei der Aufgabe vorrausgesetzt wurde?
Entscheidbare sprachen unter komplement abgeschlossen, jede kontextfreie sprache entscheidbar, jede endlich sprache regulär,
Welche typen sind immer entscheidbar / aufzählbar, etc..

[robert.n]

Also auf jeden Fall habe ich mir Folie 172 von Prof. Kohlenbach ausgedruckt. Da wird schon mal eine ganze Menge über diesen Kram ausgesagt. Allerdings ist das mit der Entscheidbarkeit/Aufzählbarkeit nicht dabei.

Entscheidbar ist aber AFAIK jede Sprache, die von irgendeinem Automaten erkannt wird und damit doch eigentlich jede von uns behandelte Sprache (entscheidbar = kann algorithmisch ermittelt werden ob ein Wort Teil der Sprache ist oder nicht). Macht ja auch Sinn irgendwie.

Naja und Aufzählbarkeit, was heißt das denn jetzt nochmal?^^
// EDIT: Aufzählbarkeit bedeutet wohl soviel wie "die Sprache kann (schrittweise) erzeugt werden", was ja dann durch einen Automaten gewährleistet ist, oder?

[linn]

naja so ganz check ich des auch ned, des ja des prob
Also wie ich das verstanden hab ist jede Sprache aufzählbar, aber nicht jede entscheidbar.
Entscheidbar heisst, dass sowohl die sprache als auch ihr komplement aufzählbar ist.
Der Automat muss also für jede beliebige eingabe terminieren.
Typ 0- sprachen terminieren aber nicht zwangsläufig auf eingaben die nicht in der Sprache enthalten sind, deswegen sind sie auch im allgemeinen unentscheidbar.
Typ3-sprachen sind immer entscheidbar, weil sie unter komplement abgeschlossen sind. (Ein Automat kann also erkennen, dass ein Wort _nicht_ teil der Sprache ist).
Gleiches gilt dann wohl auch für Typ1-Sprachen. (und damit wohl auch für Typ2-Sprachen, da die ja ne teilmenge der typ1-sprachen sind)
Also alle Sprachen sind aufzählbar, und Typ1-3-sprachen sind entscheidbar. Das ist zumindest meine Theorie :S

Und was genau aufzählbar ist, uhm...

[tzeenie]

Entscheidbar ist aber AFAIK jede Sprache, die von irgendeinem Automaten erkannt wird und damit doch eigentlich jede von uns behandelte Sprache (entscheidbar = kann algorithmisch ermittelt werden ob ein Wort Teil der Sprache ist oder nicht).

Nicht ganz - entscheidbar heißen alle Sprachen, die von einer Turingmaschine akzeptiert werden, die bei jeder Eingabe anhält. D.h. sie entscheidet das Wortproblem der Sprache in endlicher Zeit durch verwerfen oder akzeptieren. Semientscheidbar sind Sprachen, für die eine Turingmaschine alle Worte der Sprache akzeptiert, aber bei Worten die nicht in der Sprache sind nicht notwendigerweise anhält.

Naja und Aufzählbarkeit, was heißt das denn jetzt nochmal?^^

Alle Sprachen, die von einer Turingmaschine akzeptiert werden, heißen rekursiv aufzählbar. Also sind die entscheidbaren Sprachen eine echte Teilmenge der rekursiv aufzählbaren Sprachen.

Gruß!
Jens

[linn]

kann man sagen aufzählbare sprachen = {entscheidbare Sprachen} vereinigt mit {semi-entscheidbare Sprachen}?
und ist das so richtig was ich vorhin geschrieben hab? ( typ1-3 entscheidbar, typ0-3 aufzählbar)

[tzeenie]

Typ-2 ist entscheidbar - kontextfreie Grammatiken werden bspw. verwendet um Parser für Programmiersprachen zu schreiben:
Die Sprache der korrekt geschachtelten Klammerausdrücke ist bereits kontextfrei (kam auch im Skript vor, glaub ich), und es wär ja schlecht wenn das nur semientscheidbar wäre, dann würd man ja u.U. lange auf ein kompiliertes C-Programm warten!

Mist, war noch ned fertig. Typ-1 Sprachen sind iA nicht entscheidbar, werden aber durch die linear-platzbeschränkte Turingmaschine definiert.

[tzeenie]

Korrektur: Du hattest Recht, das Wortproblem kontextsensitiver Grammatiken ist doch entscheidbar, sorry! Also völlig richtig, Typ1-3 entscheidbar, Typ0 iA nicht.

[robert.n]

Danke an euch!