Ejemplos de lenguajes sin contexto con complementos sin contexto

Los lenguajes sin contexto no se cierran bajo complementación. En las conferencias se nos ha dado el mismo argumento que aquí en Wikipedia : para

$$A = \{\mathtt a^n \mathtt b^n \mathtt c^m;~m, n ∈ ℕ_0\}\quad\text{and}\quad B = \{\mathtt a^m \mathtt b^n \mathtt c^n;~m, n ∈ ℕ_0\},$$ tanto $A$ como $B$ están libres de contexto, pero su intersección $A ∩ B$ no lo es. Dado que los lenguajes libres de contexto están cerrados bajo sindicatos, tampoco pueden cerrarse bajo complementación.

Sin embargo, esto solo muestra que uno de los tres idiomas $A$ , $B$ y $\overline A \cup \overline B$ es un lenguaje sin contexto con un complemento sin contexto, pero no para cuál de estos es cierto. ¿Así que qué es lo?

Además, ¿hay un ejemplo mínimo y elegante de un lenguaje sin contexto con un complemento sin contexto, tal vez sobre un alfabeto binario?

El idioma no está libre de contexto (como se puede mostrar usando el lema de bombeo; ver aquí ). Su complemento tiene contexto (como se muestra aquí ). Esto proporciona un ejemplo simple y elegante de un lenguaje sin contexto (sobre un alfabeto binario) cuyo complemento no está libre de contexto, como solicitó.$L_1= \{ww \mid w \in \{a,b\}^*\}$$L_2 = \{a,b\}^* \setminus L_1$

El ejemplo que ves en Wikipedia: pon , . Es fácil ver que y tienen contexto definiendo un PDA; puede notar que son lenguajes deterministas sin contexto, que es una clase cerrada bajo complemento. Por lo tanto, es un lenguaje sin contexto con un complemento sin contexto .$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\}$

En la misma línea, el lenguaje no está libre de contexto, pero su complemento sí.$\{a^n b^m c^n d^m\}$