Czy języków bezkontekstowych w

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 (!?)$a^*b^*$$a,b$

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ą.$L$$\pi(L) = \{ (m,n) \mid a^mb^n \in L \}$

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 .$w_1^* \dots w_k^*$$w_1,\dots,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.$\{ a^nb^m \mid n^2 \neq m \}$$a^*b^*$

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 \leq 2$$w_1^* w_2^*$

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

$M_1 \subseteq w_1^*w_2^*$$M_2$$w_1$$w_2$$M_1\cap M_2$

$M_1 \subseteq w_1^*w_2^*$$M_2$$w_1$$w_2$$M_1 - M_2$$M_2-M_1$

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

$\{ a^i b^j : (i,j) \in A \}$$A$

$A$$\overline{A}$

$L_i \subseteq a^*b^*$