Diberikan PDA M sehingga L (M) dalam DCFL membangun DPDA N sedemikian rupa sehingga L (N) = L (M)

Apakah mungkin untuk membangun suatu algoritma yang mengambil sebagai input suatu pushdown automaton bersama dengan janji bahwa bahasa yang diterima oleh automaton ini adalah bahasa bebas bebas konteks-deterministik dan menghasilkan sebuah otomatisasi pushdown deterministic yang menerima secara tepat bahasa yang diterima oleh ? $M$ $L(M)$ $N$ $M$

Masalah setara akan membangun suatu algoritma yang mengambil sebagai masukan pushdown automata (dengan janji bahwa adalah deterministik, seperti di atas) dan pushdown automata deterministik . Outputnya adalah ya jika dan tidak jika . $M$ $L(M)$ $N$ $L(M) = L(N)$ $L(M)\neq L(N)$

Saya percaya bahwa pemecahan algoritma yang pertama akan memberikan pemecahan algoritma kedua dengan decidability of equivalence pushdown automata automata. Saya pikir solusi untuk yang kedua akan menyiratkan solusi untuk yang pertama saat kami menghitung semua automata pushdown deterministik dan menjalankan algoritma pada mereka satu per satu, setelah kami mendapatkan contoh ya kita hasilkan otomat itu.

Aku ingin tahu apakah ada yang tahu tentang ini? Mungkin itu masalah yang diketahui dan / atau memiliki solusi yang diketahui? Sebagai tambahan, saya percaya itu dapat diputuskan jika Anda memperkenalkan batasan yang mengatakan bahwa bahasa yang dihasilkan oleh PDA adalah masalah kata kelompok.

reference-request computability fl.formal-languages automata-theory Sam Jones
sumber

Determinisme dan kesetaraan adalah masalah terkenal yang tidak dapat dipastikan. Anda akan menemukannya di Hopcroft & Ullman (1979) misalnya.

Sylvain

Ya, mereka dikenal sebagai masalah yang belum diputuskan, tetapi saya tidak bertanya apakah mungkin untuk memutuskan determinisme. Kesetaraan yang saya tanyakan adalah dari PDA yang pasti menerima bahasa deterministik dan DPDA. Kecuali saya telah melewatkan sesuatu, tidak ada alasan yang jelas mengapa itu harus diputuskan, saya tidak bisa melihat mengapa itu harus mengikuti dari ketidakpastian masalah kesetaraan untuk PDA.

Sam Jones

Sayang sekali, saya membaca posting Anda terlalu cepat. Pertanyaan yang menarik sebenarnya.

Sylvain

Ambil TM $M$ deterministik dan sebuah kata $w$ . Pertimbangkan sejarah komputasinya untuk kata $w$ . Biarkan $L$ menjadi riwayat yang tidak valid (yang tidak dimulai dengan $w$ , jangan diakhiri dengan penerimaan atau tidak valid). Baik $L = A^{\ast}$ ( $M$ tidak menerima $w$ ) atau $L = A^{\ast} - \{h\}$ untuk beberapa string $h$ ( $M$ menerima $w$ dengan riwayat perhitungan $h$ ). Pertama-tama, $L$ adalah CFL yang efektif, dalam arti bahwa Anda dapat membangun tata bahasa / PDA mengenalinya. Selain itu, $L$ adalah DCFL (tidak efektif), tetapi Anda tidak dapat menunjukkan DPDA untuk itu secara efektif. Terlebih lagi, $L$ (tidak efektif) teratur.

Klarifikasi kecil:

Anda bertanya apakah masalah berikut dapat diputuskan:

diberikan PDA $M$ berjanji bahwa $L(M)$ adalah DCFL, dan DPDA $N$ menentukan apakah $L(M) = L(N)$ .

Jawabannya adalah tidak, dan faktanya fakta kuat berikut ini berlaku: Masalah berikut tidak dapat diputuskan:

$M$ $L(M)$ $L(M)=A^{\ast}$

sdcvvc
sumber

A^{*}

$A^{*}$

w

$w$

A^{*}

$A^{\ast}$

M

$M$

w

$w$

L = A^{*}

$L=A^{*}$

L = A^{*} - {h}

$L=A^{*}-\{h\}$

M

$M$

w

$w$

M

$M$

w

$w$

M

$M$

OK akhirnya.

Sylvain

Diberikan PDA M sehingga L (M) dalam DCFL membangun DPDA N sedemikian rupa sehingga L (N) = L (M)

Jawaban: