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 (!?)
Oto mój argument. Każdy język CF ma półliniowy obraz Parikha π ( L ) = { ( m , n ) ∣ a m b n ∈ L } . 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ą.
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 .
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.
Odpowiedzi:
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 .k k≤2 w∗1w∗2
Ginsburg wspomina o tych implikacjach w swojej książce.
źródło
Inny dowód wykorzystuje następującą charakterystykę udowodnioną w tej odpowiedzi :
źródło