Exemplos de linguagens livres de contexto com complementos não livres de contexto

Linguagens sem contexto não são fechadas sob complementação. Nas palestras, recebemos o mesmo argumento aqui na Wikipedia : Para ambos A e B são livres de contexto, mas sua interseção A ∩ B não é. Como as linguagens sem contexto são fechadas sob uniões, elas também não podem ser fechadas sob complementação.

No entanto, isso mostra apenas que um dos três idiomas $A$ , $B$ e $\overline A \cup \overline B$ é um idioma sem contexto com um complemento sem contexto, mas não para qual deles é verdadeiro. Então o que é?

Além disso, existe um exemplo mínimo e elegante de uma linguagem livre de contexto com um complemento não livre de contexto, talvez sobre um alfabeto binário?

O idioma não é livre de contexto (como pode ser mostrado usando o lema de bombeamento; veja aqui ). Seu complemento é livre de contexto (como mostrado aqui ). Isso fornece um exemplo simples e elegante de uma linguagem livre de contexto (sobre um alfabeto binário) cujo complemento não é livre de contexto, conforme solicitado.L 2 = { um , b } * ∖ G $L_1= \{ww \mid w \in \{a,b\}^*\}$$L_2 = \{a,b\}^* \setminus L_1$

O exemplo que você vê na Wikipedia: coloque , . É fácil ver que e estão livres de contexto, definindo um PDA; você pode observar que são linguagens determinísticas livres de contexto, que é uma classe fechada sob complemento. Portanto, é uma linguagem livre de contexto com um complemento sem contexto .B = { a m b n c n } ¯ A ¯ B ¯ A ∪ ¯ B A ∩ B = { a n b n c n$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\}$

Na mesma linha, a linguagem não é livre de contexto, mas seu complemento é.$\{a^n b^m c^n d^m\}$