Menghitung persimpangan dua NPDA jika memungkinkan

Meminta saran Raphael tentang titik-temu dua NPDA :

Biarkan dan masing-masing untuk bahasa bebas konteks dan . Dengan asumsi kita tahu bahwa bebas konteks, dapatkah kita (secara efektif) membuat NPDA untuk ? $A_1$ $A_2$ $L_1$ $L_2$ $L = L_1 \cap L_2$ $A$ $L$

Semua jenis algoritma dapat diterima, tetapi semakin praktis semakin baik.

computability automata pushdown-automata Soando
sumber

contoh L seperti itu di mana L1 / L2 tidak teratur dan persimpangan tidak kosong mungkin membantu, apakah L seperti itu ada? masalah yang agak mirip dengan NPDA (pengujian kekosongan persimpangan, pengujian kesetaraan) tidak dapat diputuskan. sarankan bermigrasi / promosikan ke tcs.se jika tidak ada jawaban yang terwujud

vzn

@vzn Saya yakin saya memiliki contoh keadaan ~ 50, saya akan mencoba mencari seseorang yang lebih minimal

soandos

Set string "setidaknya 1/3 1" dan "kurang dari 2/3 1" di atas alfabet

keduanya adalah DCFL, dan persimpangan mereka adalah CFL (dan bukan DCFL)

{0, 1}

$\{0,1\}$

sjmc

@ sjmc dapatkah Anda membuat sketsa bukti? tidak jelas bagi saya. akan terbalik jika Anda mempostingnya sebagai jawaban meskipun tidak lengkap, beberapa kemajuan

vzn

pembaruan ini tampaknya dijawab sebagai tidak dapat diputuskan di tcs.se berdasarkan pada perhitungan TM yang sewenang-wenang tersebut dapat dinyatakan sebagai persimpangan dari dua CFL.

vzn

Jawaban:

Saya pikir ini mungkin untuk subclass dari CFL yang permutasi-invarian dengan alfabet biner.

Bersesuaian ini untuk mengetik bahasa quantifier membandingkan kardinalitas dari dua set. [1] mengkarakterisasi bahasa-bahasa seperti itu yang diterima oleh DPDA oleh set semilinear yang ekuivalen, dan menyatakan pada akhirnya bahwa bahasa-bahasa kuantifikasi yang diterima oleh NPDA adalah kombinasi boolean terbatas dari bahasa-bahasa tersebut yang diterima oleh DPDA. $\langle 1,1\rangle$

Sebuah teorema van Benthem ([2]) mengatakan bahwa pushdown automata menerima jenis bilangan didefinisikan di Presburger aritmatika (yaitu didefinisikan oleh set semilinear). Jadi, jika Anda mendapatkan dua bahasa yang merupakan CFL non-deterministik (menggunakan kertas pertama untuk mengetahui Anda memiliki contoh seperti itu), persimpangan mereka juga harus menjadi CFL oleh teorema ini. $\langle 1,1\rangle$

Set semilinear yang merupakan persimpangan mereka mungkin agak sulit untuk dihitung ... tetapi, jika Anda memilikinya, [3] (hal.111-12) memberikan algoritma untuk membuat NPDA menerima bahasa berdasarkan generator dari set semilinear yang sesuai.

[1] Makoto Kanazawa. Kuantitatif monadik yang diakui oleh automata push-down deterministik . Dalam Prosiding Kolokium Amsterdam ke-19, halaman 139-146, 2013.

[2] Johann van Benthem. Esai dalam Semantik Logika . Studi dalam Linguistik dan Filsafat Volume 29, 1986, hal 151-176.

[3] Marcin Mostowski. Semantik komputasi untuk quantiers monadik . Jurnal Logika Non-Klasik Terapan, 8 (1-2): 107-121, 1998.

sjmc
sumber