Przykłady języków bezkontekstowych z uzupełnieniami bezkontekstowymi

Języki bezkontekstowe nie są zamknięte pod uzupełnieniem. W wykładach podano nam ten sam argument, co tutaj na Wikipedii :

$$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\},$$ oba $A$ i $B$ są pozbawione kontekstu, ale ich przecięcie $A ∩ B$ nie jest. Ponieważ języki bezkontekstowe są zamknięte w związkach, nie można ich również zamykać w ramach uzupełnień.

Pokazuje to jednak tylko, że jeden z trzech języków $A$ , $B$ i $\overline A \cup \overline B$ jest językiem bezkontekstowym z niekompletnym uzupełnieniem, ale nie dotyczy to jednego z tych języków. Więc co to jest?

Czy istnieje też minimalny i elegancki przykład języka bezkontekstowego z uzupełnieniem bezkontekstowym, może ponad alfabet binarny?

Język nie jest pozbawiony kontekstu (co można pokazać za pomocą lematu pompowania; patrz tutaj ). Jego uzupełnienie jest kontekstu (jak pokazano tutaj ). Daje to prosty i elegancki przykład języka bezkontekstowego (nad alfabetem binarnym), którego uzupełnienie nie jest pozbawione kontekstu, tak jak prosiłeś.$L_1= \{ww \mid w \in \{a,b\}^*\}$$L_2 = \{a,b\}^* \setminus L_1$

Przykład, który widzisz na Wikipedii: wpisz , . Łatwo jest zauważyć, że i są pozbawione kontekstu poprzez zdefiniowanie PDA; można zauważyć, że są to deterministyczne języki bezkontekstowe, które są klasą zamkniętą pod dopełnieniem. Dlatego jest językiem bezkontekstowym z niekontekstowym uzupełnieniem .$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\}$

Podobnie język nie jest pozbawiony kontekstu, ale uzupełnieniem jest.$\{a^n b^m c^n d^m\}$