Apakah kesetaraan bahasa bebas konteks yang ambigu dapat dipilih?

19

Sudah diketahui bahwa masalah kesetaraan tidak dapat diputuskan untuk bahasa bebas konteks umum. Namun, semua bukti dari fakta ini yang saya sadari tampaknya melibatkan beberapa tata bahasa bebas konteks yang ambigu. Untuk alasan ini, saya ingin bertanya apakah diketahui apakah masalahnya tetap tidak dapat diputuskan saat membatasi diri ke bahasa bebas konteks yang jelas . Yaitu, mengingat dua tata bahasa bebas konteks yang apriori diberikan untuk tidak ambigu, apakah dapat diputuskan apakah mereka setara atau tidak?

Saya menemukan masalah ini sedikit menarik, karena diketahui bahwa kesetaraan dapat ditentukan untuk bahasa bebas konteks deterministik , meskipun hasil ini masih jauh dari sepele ... Di sisi lain, mungkin ada beberapa alasan sederhana untuk keraguan yang telah saya tentukan. menghadap.

fl.formal-languages grammars context-free decidability undecidability Jára Cimrman
sumber
3
Inklusi tidak dapat diputuskan: pdfs.semanticscholar.org/afdb/…
Peter Leupold
4
@PeterLeupold Ya, tetapi penyertaan juga tidak dapat dipastikan untuk bahasa bebas konteks bebas, jadi ini cukup mudah (artikel yang Anda tautkan hanya memberikan bukti tanpa menggunakan fakta ini). Namun, kesetaraan tampaknya jauh lebih menarik, karena ini dapat ditentukan untuk bahasa bebas konteks bebas deterministik dan tidak dapat diputuskan untuk bahasa umum bebas konteks umum ...
Jára Cimrman
3
Namun demikian, saya mulai curiga bahwa masalah ini mungkin terbuka: bukti kepastian keputusan hampir tidak diketahui, karena yang untuk CFL deterministik cukup rumit; di sisi lain, ketidakpastian akan menyiratkan keraguan tentang kesetaraan seri aljabar dalam variabel nonkomutatif, yang, jika saya memahami semuanya dengan benar, harus menjadi masalah terbuka. N
Jára Cimrman

Jawaban:

9

Ini saat ini merupakan masalah terbuka. Seperti yang ditunjukkan dengan benar, jika itu dapat ditentukan, maka orang akan mengharapkan bukti menjadi sulit karena generalisasi masalah kesetaraan DPDA yang terkenal. Di sisi lain, argumen klasik untuk keraguan terhadap masalah universalitas CFL memanfaatkan bahasa yang secara inheren ambigu, dan karenanya orang perlu ide-ide baru untuk menunjukkan keraguan.

Izinkan saya menunjukkan bahwa masalah universalitas untuk UCFL adalah decidable (di PSPACE), menggunakan fungsi pembangkit [1].

REFERENSI

[1] N. Chomsky dan MP Schützenberger, Teori Aljabar Bahasa Bebas Konteks, Pemrograman Komputer dan Sistem Formal, 1963.

Lorenzo
sumber
2
Saya pikir maksud Anda secara inheren bahasa ambigu .
Emil Jeřábek mendukung Monica
memang, terima kasih @ EmilJeřábek karena telah menemukan ini
Lorenzo