Komplement einer kontextfreien Sprache

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

Komplement einer kontextfreien Sprache
Hey, eine Frage:

Gegeben: “Es gibt eine kontextfreie Sprache L über dem Alphabet Σ, so dass das Komplement von L, also die Sprache Σ*\L, unentscheidbar ist.”

Alle entscheidbaren Sprachen sind ja auch bezüglich ihres Komplements abgeschlossen. Aber kontextfreie Sprachen sollen ja mit ihrem Komplement nicht abgeschlossen sein, was also heißt, dass das Komplement einer kontextfreien Sprache nicht unbedingt kontextfrei sein muss. Heißt der erste Satz etwa, dass das Komplement einer entscheidbaren Sprache immer auch selbst entscheidbar ist? Und gilt das auch für kontextfreie Sprachen oder nur reguläre Sprachen?


Die Aussage ist einfach falsch.
Ja, das Komplement einer entscheidbaren Sprache ist entscheidbar, somit auch das Wortproblem von regulaeren, kontextfreien (und kontextsensitiven) Sprachen.