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

11

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

A={anbncm; m,n0}andB={ambncn; m,n0},
oba A i B są pozbawione kontekstu, ale ich przecięcie AB 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 A¯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?

k.stm
źródło

Odpowiedzi:

16

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ś.L1={www{a,b}}L2={a,b}L1

DW
źródło
13

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={anbncm}B={ambncn}A¯B¯A¯B¯AB={anbncn}

Podobnie język nie jest pozbawiony kontekstu, ale uzupełnieniem jest.{anbmcndm}

sdcvvc
źródło
Pytanie dotyczy „minimalistycznego i eleganckiego”, a przykłady te są znacznie bardziej złożone niż prosty przykład podany przez @DW w jego odpowiedzi.
David Richerby,
2
@David Richerby: IMO przykład może być bardziej elegancki niż lub , ale trudniej jest udowodnić, podczas gdy pozostałe dwa są mechaniczne. {ww}¯{anbncn}¯{anbncmdm}¯
sdcvvc,
Musiałeś oznaczać w drugim przykładzie. {anbmcndm}
Yuval Filmus,
Tak, dziękuję za poprawkę (widzę, że popełniłem ten sam błąd w komentarzu, za późno, aby go teraz edytować).
sdcvvc