Guten Tag,
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?
Hallo,
Warum ist das Komplement einer kontextfreien Sprache nicht
zwangläufig kontextfrei?
weil kontextfreie Sprachen von nichtdeterministischen Automaten erkannt werden, und die nicht einfach invertierbar sind.
Einen formaleren Beweis gibt es auf http://moritz.faui2k3.org/files/automaten.pdf Seite 51.
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* - L1Normalerweise würd ich jetzt mit dem Pumping Lemma
argumentieren, weiß aber leider nicht wie ich hier ansetzen
soll.
Das PL hilft dir hier nicht weiter, weil man damit nur zeigen kann, welche Sprachen nicht regulaer oder kontextfrei sind. Wenn eine Sprache das PL erfuellt, weiss man aber noch nicht, ob sie tatsaechlich regulaer oder kontextfrei ist.
Gruesse,
Moritz