Beispiele für kontextfreie Sprachen mit nicht kontextfreien Ergänzungen

11

Kontextfreie Sprachen werden nicht unter Ergänzung geschlossen. In den Vorlesungen wurde uns das gleiche Argument wie hier auf Wikipedia gegeben : Für sowohl als auch sind kontextfrei, ihr Schnittpunkt jedoch nicht. Da kontextfreie Sprachen unter Gewerkschaften geschlossen werden, können sie auch nicht unter Ergänzung geschlossen werden.

A={anbncm; m,n0}andB={ambncn; m,n0},
ABAB

Dies zeigt jedoch nur, dass eine der drei Sprachen , und eine kontextfreie Sprache mit einer nicht kontextfreien Ergänzung ist, für die jedoch keine gilt. Also, was ist es?ABA¯B¯

Gibt es auch ein minimales und elegantes Beispiel für eine kontextfreie Sprache mit einer nicht kontextfreien Ergänzung, möglicherweise über einem binären Alphabet?

k.stm.
quelle

Antworten:

16

Die Sprache ist nicht kontextfrei (wie mit dem Pump-Lemma gezeigt werden kann; siehe hier ). Sein Komplement L 2 = { a , b } L 1 ist kontextfrei (wie hier gezeigt ). Dies ist ein einfaches und elegantes Beispiel für eine kontextfreie Sprache (über ein binäres Alphabet), deren Ergänzung nicht kontextfrei ist, wie Sie es gewünscht haben.L1={www{a,b}}L2={a,b}L1

DW
quelle
13

Das Beispiel, das Sie auf Wikipedia sehen: Setzen Sie , B = { a m b n c n } . Es ist leicht zu sehen ¯ A und ¯ B sind kontextfrei durch die Definition eines PDA; Sie können feststellen, dass es sich um deterministische kontextfreie Sprachen handelt, bei denen es sich um eine Klasse handelt, die unter Komplement geschlossen wird. Daher ¯ A¯ B ist eine kontextfreie Sprache mit einem nicht kontextfreien Komplement A B = { aA={anbncm}B={ambncn}A¯B¯A¯B¯ .AB={anbncn}

In gleicher Weise ist die Sprache nicht kontextfrei, aber ihre Ergänzung ist.{anbmcndm}

sdcvvc
quelle
Die Frage verlangt nach "minimal und elegant" und diese Beispiele sind viel komplexer als das einfache Beispiel, das @DW in seiner Antwort gegeben hat.
David Richerby
2
@ David Richerby: IMO ist das Beispiel vielleicht eleganter als ¯ { a n b n c n } oder ¯ { a n b n c m d m } , aber es ist komplexer zu beweisen, während die anderen beiden sind mechanisch. {ww}¯{anbncn}¯{anbncmdm}¯
SDCVVC
Sie müssen in Ihrem zweiten Beispiel gemeint haben . {anbmcndm}
Yuval Filmus
Ja, danke für die Korrektur (ich sehe, dass ich den gleichen Fehler im Kommentar gemacht habe, zu spät, um ihn jetzt zu bearbeiten).
SDCVVC