Apakah bahasa bebas konteks dalam

Bahasa bebas konteks tidak ditutup di bawah pelengkap, kami tahu itu.

Sejauh yang saya mengerti, bahasa bebas konteks yang merupakan bagian dari $a^*b^*$ untuk beberapa huruf $a,b$ ditutup di bawah pelengkap (!?)

Inilah argumen saya. Setiap bahasa CF $L$ memiliki gambar Parikh semi-linear $\pi(L) = \{ (m,n) \mid a^mb^n \in L \}$ . Set semilinear ditutup dengan komplemen. Himpunan vektor yang mewakili himpunan semi-linier dapat dengan mudah diubah menjadi tata bahasa linier.

Pertanyaan. Apakah ada referensi yang mudah diakses tentang fakta ini?

Secara teknis bahasa-bahasa ini disebut dibatasi , yaitu, bagian dari $w_1^* \dots w_k^*$ untuk beberapa kata $w_1,\dots,w_k$ .

Motivasi saya untuk pertanyaan ini adalah dari pertanyaan baru-baru ini tentang konteks-kelayakan $\{ a^nb^m \mid n^2 \neq m \}$ . Its pelengkap dalam $a^*b^*$ tampaknya lebih mudah untuk menangani.

Karakterisasi bahasa terikat-konteks bebas ini disebabkan oleh Ginsburg ("Teori Matematika Bahasa Bebas Konteks"), dan muncul sebagai Corollary 5.3.1 dalam bukunya. Untuk umum ada beberapa batasan pada set semilinear, tetapi untuk k ≤ 2 pembatasan ini selalu dipenuhi, dan dengan demikian mudah untuk menyimpulkan bahwa pelengkap bahasa seperti itu (dalam w ∗ 1 w ∗ 2 ) bebas konteks .$k$$k \leq 2$$w_1^* w_2^*$

Ginsburg menyebutkan implikasi ini dalam bukunya.

Konsuler 5.6.1 Jika dan M 2 adalah bahasa [bebas konteks], w 1 dan w 2 kata, maka M 1 ∩ M 2 adalah bahasa [bebas konteks].$M_1 \subseteq w_1^*w_2^*$$M_2$$w_1$$w_2$$M_1\cap M_2$

Konsol 5.6.2 Jika dan M 2 adalah bahasa [bebas konteks], w 1 dan w 2 kata, maka M 1 - M 2 dan M 2 - M 1 adalah [bebas konteks] bahasa.$M_1 \subseteq w_1^*w_2^*$$M_2$$w_1$$w_2$$M_1 - M_2$$M_2-M_1$

Bukti lain menggunakan karakterisasi berikut yang dibuktikan dalam jawaban ini :

Bahasa bebas konteks jika A dapat didefinisikan dalam aritmatika Presburger.$\{ a^i b^j : (i,j) \in A \}$$A$

Jelas adalah didefinisikan dalam Presburger IFF aritmatika ¯ A adalah didefinisikan dalam Presburger aritmatika.$A$$\overline{A}$

$L_i \subseteq a^*b^*$