Warum ist das Komplement einer kontextfreien Sprache nicht zwangläufig kontextfrei?

gefragt von am 05.11.2009 um 10:43 Uhr

Warum ist das Komplement einer kontextfreien Sprache nicht zwangläufig kontextfrei?

Ich versuche das gerade zu ergründen, finde aber kaum was im Netz dazu. Nehmen wir also an, wir haben eine kontextfreie Sprache L1, so dass das Komplement L2 = Komplement(L1) = Sigma* - L1

Normalerweise würd ich jetzt mit dem Pumping Lemma argumentieren, weiß aber leider nicht wie ich hier ansetzen soll. Kann jemand helfen?

Hier finden Sie weitere Fragen zu den Themen:

Grammatik x 1.599 Informatik x 943 Pumping Lemma x 1

Antworten

Kommentare ein-/ausblenden

beantwortet von am 6. November 2009 18:56

Hi, ich hab ein pdf gefunden, in dem begründet wird, warum kontextfreie Sprachen nicht bezügl Durchschnitt abgeschlossen sind. Die Begründung für Komplementbildung wird dann darauf zurückgeführt:

http://www.ifi.uzh.ch/cl/schacht/iii2.pdf

Allerdings steht bei Wikipedia: "Das Problem, ob der Schnitt zweier kontextfreier Grammatiken G1,G2 eine kontextfreie Grammatik ist, ist nicht entscheidbar."

Das wiederspricht sich natürlich... allerdings find ich die Begründung aus dem pdf auf den ersten Blick einleuchtend. Würd mich interressieren, falls du mehr dazu rausbekommst. Gruß Matze