Czy języków bezkontekstowych w

20

Wiemy, że języki bezkontekstowe nie są zamknięte pod uzupełnieniem.

O ile mi zrozumieć, języków bezkontekstowych, które są podzbiorem * b * dla niektórych liter a , b są zamknięte pod dopełniacza (!?)aba,b

Oto mój argument. Każdy język CF ma półliniowy obraz Parikha π ( L ) = { ( m , n ) a m b nL } . Zestawy półliniowe są zamknięte pod dopełnieniem. Zbiór wektorów reprezentujących zbiór półliniowy można łatwo przekształcić w gramatykę liniową.Lπ(L)={(m,n)ambnL}

Pytanie. Czy istnieje łatwo dostępne odniesienie do tego faktu?

Technicznie języki te nazywane są ograniczonymi , tj. Podzbiorem dla niektórych słów w 1 , , w k .w1wkw1,,wk

Moją motywacją do tego pytania jest ostatnie pytanie dotyczące kontekstowości . Jej uzupełnieniem wewnątrz a * b * wydaje się łatwiejsze w obsłudze.{anbmn2m}ab

Hendrik Jan
źródło
Czy sprawdziłeś „Matematyczną teorię języków bezkontekstowych” Ginsburga? Najwyraźniej Twierdzenie 5.4.2 podaje charakterystykę ograniczonych języków bezkontekstowych, do których się odwołujesz, i założę się, że Ginsburg wspomniałby o implikacji dla uzupełnienia ograniczonych języków bezkontekstowych (w przypadku dwuwymiarowym).
Yuval Filmus

Odpowiedzi:

12

Ta charakterystyka ograniczonych języków bezkontekstowych wynika z Ginsburga („Matematyczna teoria języków bezkontekstowych”) i pojawia się jako następstwo w jego książce. W przypadku ogólnego istnieją pewne ograniczenia dotyczące zestawów półliniowych, ale dla k 2 ograniczenia te są zawsze spełnione, dlatego łatwo jest wydedukować, że dopełnienie takiego języka (w w 1 w 2 ) jest pozbawione kontekstu .kk2w1w2

Ginsburg wspomina o tych implikacjach w swojej książce.

M1w1w2M2w1w2M1M2

M1w1w2M2w1w2M1M2M2M1

Yuval Filmus
źródło
2

Inny dowód wykorzystuje następującą charakterystykę udowodnioną w tej odpowiedzi :

{aibj:(i,j)A}A

AA¯

Liab

Yuval Filmus
źródło