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

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.

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?$A$$B$$\overline A \cup \overline 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?

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.$L_1= \{ww \mid w \in \{a,b\}^*\}$$L_2 = \{a,b\}^* \setminus L_1$

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 = { $A=\{a^n b^n c^m\}$$B=\{a^m b^n c^n\}$$\overline{A}$$\overline{B}$$\overline{A} \cup \overline{B}$ .$A \cap B=\{a^n b^n c^n\}$

In gleicher Weise ist die Sprache nicht kontextfrei, aber ihre Ergänzung ist.$\{a^n b^m c^n d^m\}$