Apakah ada ekstensi ekspresi reguler yang menangkap konteks bahasa bebas?

Dalam banyak makalah yang melibatkan tata bahasa bebas konteks (CFG), contoh-contoh tata bahasa yang disajikan di sana sering mengakui karakterisasi yang mudah dari bahasa yang mereka hasilkan. Sebagai contoh:

$S \to a a S b$
$S \to$

menghasilkan $\{ a^{2i} b^i | i \geq 0\}$ ,

$S \to a S b$
$S \to a a S b$
$S \to$

menghasilkan $\{ a^i b^j \mid i \geq j \geq 0 \}$ , dan

$S \to a S a$
$S \to b S b$
$S \to$

menghasilkan $\{ w w^R \mid w \in (a|b)^* \}$ , atau ekuivalen $\{ ((a|b)^*)_1 ((a|b)^*)_2 \mid p_1 = p_2^R \}$ (di mana $p_1$ mengacu ke bagian ditangkap oleh $(...)_1$ ).

Contoh di atas semua dapat dihasilkan dengan menambahkan indeks ( $a^i$ ), batasan sederhana pada indeks ini ( $i > j$ ) dan pencocokan pola dengan ekspresi reguler. Ini membuat saya bertanya-tanya apakah semua bahasa bebas konteks dapat dihasilkan oleh beberapa ekstensi dari ekspresi reguler.

Apakah ada ekstensi ekspresi reguler yang dapat menghasilkan semua atau beberapa bagian signifikan dari konteks bahasa bebas?

Ya ada. Tetapkan ekspresi bebas konteks menjadi istilah yang dihasilkan oleh tata bahasa berikut:

$$\begin{array}{lcll} g & ::= & \epsilon & \mbox{Empty string}\\ & | & c & \mbox{Character $c$ in alphabet $\Sigma$} \\ & | & g \cdot g & \mbox{Concatenation} \\ & | & \bot & \mbox{Failing pattern} \\ & | & g \vee g & \mbox{Disjunction}\\ & | & \mu \alpha.\; g & \mbox{Recursive grammar expression} \\ & | & \alpha & \mbox{Variable expression} \end{array}$$

Ini semua konstruktor untuk bahasa reguler kecuali bintang Kleene, yang digantikan oleh operator titik tetap umum $\mu \alpha.\;g$$g\ast \triangleq \mu \alpha.\;\epsilon \vee g\cdot\alpha$

Interpretasi dari ekspresi bebas konteks memerlukan akuntansi untuk interpretasi variabel bebas. Jadi tentukan lingkungan menjadi peta dari variabel ke bahasa (yaitu, himpunan bagian dari ), dan biarkan menjadi fungsi yang berperilaku seperti pada semua input kecuali , dan yang mengembalikan bahasa untuk .Σ ∗ [ ρ | α : L ] ρ α L $\rho$$\Sigma^*$$[\rho|\alpha:L]$$\rho$$\alpha$$L$$\alpha$

Sekarang, tentukan interpretasi dari ekspresi bebas konteks sebagai berikut:

$$\newcommand{\interp}[2]{[\![{#1}]\!]\;{#2}} \newcommand{\setof}[1]{\left\{#1\right\}} \newcommand{\comprehend}[2]{\setof{{#1}\;\mid|\;{#2}}} \begin{array}{lcl} \interp{\epsilon}{\rho} & = & \setof{\epsilon} \\ \interp{c}{\rho} & = & \setof{c} \\ \interp{g_1\cdot g_2}{\rho} & = & \comprehend{w_1 \cdot w_2}{w_1 \in \interp{g_1}{\rho} \land w_2 \in \interp{g_2}{\rho}} \\ \interp{\bot}{\rho} & = & \emptyset \\ \interp{g_1 \vee g_2}{\rho} & = & \interp{g_1}{\rho} \cup \interp{g_2}{\rho} \\ \interp{\alpha}{\rho} & = & \rho(\alpha) \\ \interp{\mu \alpha.\; g}{\rho} & = & \bigcup_{n \in \mathbb{N}} L_n \\ \mbox{where} & & \\ L_0 & = & \emptyset \\ L_{n+1} & = & L_n \cup \interp{g}{[\rho|\alpha:L_n]} \end{array}$$

Menggunakan teorema Knaster-Tarski, mudah untuk melihat bahwa penafsiran adalah yang paling tidak diperbaiki dari ekspresi.$\mu \alpha.g$

Sangat mudah (meskipun tidak sepenuhnya sepele) untuk menunjukkan bahwa Anda dapat memberikan ekspresi bebas konteks yang berasal dari bahasa yang sama dengan tata bahasa bebas konteks apa pun, dan sebaliknya. Ketidakpastian timbul dari kenyataan bahwa ekspresi bebas konteks telah menyarangkan titik tetap, dan tata bahasa bebas konteks memberi Anda satu titik tetap atas tupel. Ini membutuhkan penggunaan lemma Bekic, yang mengatakan dengan tepat bahwa titik tetap bersarang dapat dikonversi menjadi titik tetap tunggal atas suatu produk (dan sebaliknya). Tapi itu satu-satunya kehalusan.

EDIT: Tidak, saya tidak tahu referensi standar untuk ini: Saya mengerjakannya untuk kepentingan saya sendiri. Namun, ini adalah konstruksi yang cukup jelas sehingga saya yakin ini telah ditemukan sebelumnya. Beberapa Googling biasa mengungkapkan karya Joost Winter, Marcello Bonsangue, dan makalah Jan Rutten baru -baru ini, Bahasa Bebas Konteks, secara bilangan bulat , di mana mereka memberikan varian definisi ini (mengharuskan semua titik tetap untuk dijaga) yang mereka juga sebut sebagai ekspresi bebas konteks.

Ada pertanyaan terkait erat (dan beberapa jawaban) pada MathOverflow tentang bahasa yang fungsi-fungsinya menghasilkan holonomis .

Yang menarik, definisi Neel tentang semantik atas sesuai persis dengan bukti (konstruktif) dari keberadaan solusi Spesies untuk persamaan Spesies rekursif melalui teorema Spesies implisit. Sayangnya, garis besar buktinya juga harus mengandung kesalahan yang halus, karena ada kasus di mana hal-hal menjadi 'tak terbatas'. Dengan kata lain, ada kondisi pada Jacobian dari transformasi yang didefinisikan oleh tata bahasa menjadi non-tunggal yang diperlukan. Ini mungkin mengapa Bonsangue-Rutten memerlukan poin tetap untuk dijaga, sebagai salah satu cara untuk memastikan kondisi ini pada Jacobian.$\mu$

Kami baru saja menerbitkan garis besar kerangka kerja yang akan melakukan hal itu. Lihat di bawah comp.compiler , di mana saya mengirim pemberitahuan beserta beberapa tautan.

Perkembangan baru bekerja dari Chomsky-Schuetzenberger Theorem dan dapat dianggap sebagai penyelesaian dari hasil ini. Chomsky, sendiri, telah diberitahu tentang perkembangan dan menunjukkan keinginan untuk "mengejar ketinggalan".

Seiring dengan perkembangan ini, kami juga menetapkan kesetaraan dua formulasi terpisah untuk ekspresi bebas konteks - yang merupakan perpanjangan / penyelesaian dari bentuk mu-kalkulus "titik paling tidak tetap" (awalnya oleh Gruska, Yntema dan McWhirter) - yang menerima semacam rumusan akhir pada tahun 2014 - dan yang lainnya diterbitkan pada tahun 2008.