Komplement einer nicht kontextfreien Sprache?
Hallo,
ich soll in einer Aufgabe entscheiden, ob bestimmte Sprachen kontextfrei sind oder nicht (Aufgabe 1: L1 = {a^n b a^n b a^n | n aus Nat} und Aufgabe 2: L2 = Das Komplement von L1).
Mittels des Pumping Lemmas für kontextfreie Sprachen konnte ich zeigen, dass L1 nicht kontextfrei ist. Wie komme ich nun aber auf eine Lösung bei Aufgabe 2? Mir ist bewusst, dass kontextfreie Sprachen nicht im Komplement abgeschlossen sind, also kann die komplementierte Sprache ja auch kontextfrei sein.
Vielen Dank im Voraus!
1 Antwort
Wenn ich mich richtig erinnere ist das (oder ähnliche Sprachen wie a^nb^nc^n) das klassische Beispiel für nicht kontextfreie Sprachen mit einem kontextfreien Komplement.
Was in solchen Fällen meist gut funktioniert, ist mehrere kontextfreie Sprachen zu bilden, welche unter Vereinigung dieses Komplement ergeben. Zum Beispiel könnte man die Vereinigung dieser Sprachen nehmen:
- { w | w hat nicht die Form a^i b a^j b a^k }
- { a^i b a^j b a^k | i ist ungleich j }
- { a^i b a^j b a^k | j ist ungleich k }
Dafür sollte man dann relativ leicht Grammatiken oder Automaten finden. Bzw. für die letzten beiden reicht sogar eine Grammatik wenn man den Abschluss unter Konkatenation nutzt.