Warum ist komplement kontextfreien sprache nicht zwangläufig kontextfrei

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 = Sigma* - L1 Normalerweise würd ich jetzt mit dem Pumping Lemma argumentieren, weiß aber leider nicht wie ich hier ansetzen soll. Kann jemand helfen?

1 Antworten zur Frage

Bewertung: 4 von 10 mit 1581 Stimmen
Videos zum Thema
YouTube Videos

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

Dazu ist vielleicht folgender Link hilfreich:
Kontextfreie Sprache – Wikipedia
Hab ich mir schon angeguckt, hilft mir aber leider nicht auf die Sprünge.
Du meinst sicher den Abschnitt "Komplement" oder?