Exemples de langages sans contexte avec des compléments sans contexte

Les langues sans contexte ne sont pas fermées par complémentation. Dans les conférences, on nous a donné le même argument qu'ici sur Wikipédia : pour et sont tous deux sans contexte, mais leur intersection ne l'est pas. Étant donné que les langues sans contexte sont fermées sous les unions, elles ne peuvent pas être fermées également par complémentation.

Cependant, cela montre seulement que l'un des trois langages , et est un langage sans contexte avec un complément non sans contexte, mais pas pour lequel de ces derniers cela est vrai. Alors c'est quoi?$A$$B$$\overline A \cup \overline B$

Existe-t-il également un exemple minimal et élégant de langage sans contexte avec un complément non contextuel, peut-être sur un alphabet binaire?

La langue n'est pas sans contexte (comme on peut le voir en utilisant le lemme de pompage; voir ici ). Son complément est sans contexte (comme illustré ici ). Cela donne un exemple simple et élégant d'une langue sans contexte (sur un alphabet binaire) dont le complément n'est pas sans contexte, comme vous l'avez demandé.$L_1= \{ww \mid w \in \{a,b\}^*\}$$L_2 = \{a,b\}^* \setminus L_1$

L'exemple que vous voyez sur Wikipedia: mettez , . Il est facile de voir que et sont hors contexte en définissant un PDA; vous pouvez noter qu'il s'agit de langages déterministes sans contexte, qui est une classe fermée sous complément. Par conséquent, est un langage sans contexte avec un complément non contextuel .$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\}$

Dans la même veine, le langage n'est pas dépourvu de contexte mais son complément l'est.$\{a^n b^m c^n d^m\}$