Apakah ada DCFL yang paling sulit?

Greibach terkenal didefinisikan bahasa , yang disebut versi non-deterministik dari , sehingga setiap CFL adalah gambar morphic kebalikan dari . Apakah ada pernyataan serupa dengan DCFL, mungkin dengan pembatasan morfisme diizinkan? $H$ $D_2$ $H$

(Lihat, misalnya, M. Autebert, J. Berstel, dan L. Boasson. Bahasa bebas konteks dan automata pushdown. Dalam R. Rozenberg dan A. Salomaa, editor, Buku Pegangan Bahasa Resmi, volume I, bab 3. Springer Verlag , 1997.)

fl.formal-languages open-problem context-free nondeterminism hard-instances Michaël Cadilhac
sumber

Jawaban:

Karakterisasi homomorfisme yang identik dari DCFL tampaknya tidak mungkin. Berikut ini diambil dari kertas asli Greibach .

$h^{-1}(L_0)$ $h^{-1}(L_0-\{e\})$ $h$

The kertas 7 adalah versi konferensi kertas. Dalam versi konferensi, Teorema 4.2 menyatakan bahwa "Keluarga bahasa bebas konteks deterministik bukan AFDL utama".

Namun beberapa karakterisasi analog masih dimungkinkan. Okhotin memberikan karakterisasi homomorfik dari tata bahasa konjungtif dan Boolean. Untuk DCFL masalahnya tampaknya terbuka. Berikut ini adalah kesimpulan dari makalah Okhotin (dari 2013).

Setiap keluarga bahasa yang ditutup dengan homomorfisma terbalik berpotensi memiliki analogi karakterisasi homomorfis terbalik Greibach. Pertanyaannya adalah, keluarga mana yang memilikinya? Mungkinkah itu ada untuk varian linear, deterministik atau tidak ambigu dari tata bahasa biasa (bebas konteks)? Mungkinkah ada karakterisasi semacam itu untuk tata bahasa konjungtif linier, tata bahasa konjungtif yang tidak ambigu, dll.?

Mateus de Oliveira Oliveira
sumber

Terima kasih! Namun, saya tahu bahwa DCFL bukan prinsipal; inilah mengapa saya membiarkan morfisme dibatasi jika diperlukan - Saya dapat lebih akurat mengatakan pertanyaan saya sebagai: apa kelas terkecil dari fungsi F yang memiliki bahasa H di mana F (H) adalah himpunan semua DCFL - memberi atau mengambil beberapa penutupan tambahan.

Michaël Cadilhac

Baik. Saya mengedit jawaban saya. Tampaknya bagi DCFL ini adalah masalah terbuka.

Mateus de Oliveira Oliveira

Lucunya, saya tahu betul artikel Okhotin, tetapi tidak menyadari bahwa ia secara eksplisit merujuk pada masalahnya! Kalau begitu, saya tidak yakin apa yang harus dilakukan di sini; yakin, itu adalah jawaban yang valid untuk saat ini , tetapi haruskah dibiarkan terbuka sampai diselesaikan?

Michaël Cadilhac

Saya tidak tahu apa itu polisi situs tentang meminta solusi untuk masalah terbuka. Secara pribadi, jika seseorang menunjuk saya bahwa masalah yang saya minati terbuka selama bertahun-tahun, maka saya akan menerima jawabannya. Pendapat saya adalah bahwa dalam hal ini lebih tepat untuk melihat pertanyaan sebagai permintaan referensi. Tetapi mungkin ada titik pandang yang berbeda sehubungan dengan ini. Saya pikir diskusi ini di meta.cstheory mungkin membantu meta.cstheory.stackexchange.com/questions/1058/...

Mateus de Oliveira Oliveira

Tentu saja saya tidak keberatan Anda menerima jawabannya. Memang itu jawaban yang sangat menarik. Namun walaupun jenis jawaban sesuai dengan judulnya, ini sangat berbeda dari pertanyaan itu sendiri, karena pengurangan ruang log jauh lebih kuat daripada homomorfisme.

Mateus de Oliveira Oliveira

$L_0^{(2)}$ $\{a, \bar{a}, b, \bar{b}, \#, [, ]\}$

γ_{0} [\bar{a} γ_{a}^{(1)} # \bar{b} γ_{b}^{(1)}] \dots [\bar{a} γ_{a}^{(k)} # \bar{b} γ_{b}^{(k)}],

$\gamma_0\;[\bar{a}\gamma_a^{(1)}\#\bar{b}\gamma_b^{(1)}]\;\cdots\; [\bar{a}\gamma_a^{(k)}\#\bar{b}\gamma_b^{(k)}]\enspace,$

$\gamma_0, \gamma_a^{(i)}, \gamma_b^{(i)}$ $\{a, \bar{a}, b, \bar{b}\}$ $w_1w_2\cdots w_k \in \{a, b\}^k$ $\gamma_0 \; \bar{w_1}\gamma_{w_1}^{(1)} \cdots \bar{w_k}\gamma_{w_k}^{(k)}$

$L_0^{(2)}$ $L_0^{(2)}$ $L_0^{(2)}$

Seperti yang disebutkan oleh kontributor Mateus de Oliveira Oliveira, DCFL bukan AFL utama, dan tidak diketahui apakah ada karakterisasi yang tepat yang melibatkan penutupan satu bahasa dalam beberapa operasi.

Michaël Cadilhac
sumber

Kertas

J.-M. Autebert, Une note sur le cylindre des langages déterministes, Theoretical Computer Science 8 (1979), 395-399

memberikan bukti singkat dari hasil berikut (dikreditkan ke Greibach) yang tampaknya menjawab pertanyaan Anda:

$L$ $C$ $h$ $R$ $C = h^{-1}(L)\cap R$

J.-E. Pin
sumber