Membangun semua bahasa bebas konteks dari satu set bahasa dasar dan properti penutup?

Salah satu cara melihat ekspresi reguler adalah sebagai bukti konstruktif dari fakta berikut: adalah mungkin untuk membangun bahasa reguler dengan memulai dengan sekelompok kecil bahasa dan menggabungkannya melalui set kecil, properti penutupan tertutup. Khususnya, jika kita mulai dengan bahasa kosong, bahasa yang berisi string kosong, dan bahasa semua string karakter tunggal, kita dapat mengumpulkan semua bahasa reguler yang mungkin menggunakan gabungan, penggabungan, dan bintang Kleene.

Apakah ada seperangkat bahasa dasar dan properti penutup yang dapat digunakan untuk menghasilkan semua dan hanya bahasa bebas konteks? (Untuk memperjelas: Saya tidak bertanya apakah Anda dapat menulis ekspresi reguler untuk semua CFL, yang saya tahu tidak mungkin. Sebaliknya, saya bertanya-tanya apakah ada cara untuk merancang kerangka kerja yang mirip ekspresi reguler untuk CFL berdasarkan pada prinsip dasar yang sama.)

Itu mungkin, tetapi mungkin tidak persis seperti yang Anda tanyakan. Sebagai permulaan, bahasa Dyck dari semua string tanda kurung yang cocok di atas dua pasangan tanda kurung, ucapkan , atau lebih abstrak .$D_2$$\{ [,], (,) \}$$a_1,b_1,a_2,b_2$

Kemudian setiap bahasa bebas konteks dapat diperoleh dari menggunakan homomorfisma, homomorfisma terbalik dan persimpangan dengan bahasa biasa. Bahasa bebas konteks disebut "kerucut utama yang dihasilkan oleh ", dalam buku-buku lama yang dilambangkan . Lihat pertanyaan terkait: " Bahasa apa yang dikenali oleh mesin satu-counter? "$D_2$$D_2$$\mathcal{M}(D_2)$

Faktanya, kita hanya perlu satu dari setiap operasi (dipilih dengan baik). Setiap CFL dapat ditulis , di mana , adalah homomorfisme, dan adalah bahasa biasa. Secara intuitif, adalah sebuah program dari PDA, memetakan setiap instruksi untuk surat itu dibaca, untuk push dan pop operasi stack. Akhirnya mengkode perilaku stack yang tepat.$g(h^{-1}(D_2) \cap R)$$g$$h$$R$$R$$g$$h$$D_2$

Hasil ini terkait dengan Teorema Chomsky-Schützenberger (atau seperti yang dapat dilihat di wikipedia, salah satunya). Pernyataan yang ditautkan di sini dalam wikipedia (a) tidak memerlukan homomorfisme terbalik, sementara (b) tidak terbatas pada dua pasang kurung. Teorema jenis ini berasal dari area "Abstract Families of Automata", di mana Ginsburg dan Greibach adalah nama-nama penting. Hasil terkait oleh Nivat menyatakan bahwa operasi dari bentuk untuk fixed adalah transduksi state hingga.$L \mapsto g(h^{-1}(L) \cap R)$$g,h,R$