Apakah DCFL ditutup dengan pembalikan?

Menurut grafik ini , DCFL ditutup di bawah pembalikan.

Namun, saya tidak yakin sebagai bukti intuitif (membalikkan panah dari mesin negara hingga dan mengalihkan dorongan dan muncul) untuk ini tampaknya tergantung pada non-determinisme dalam memilih transisi nol untuk mengambil dari keadaan awal (karena keadaan awal baru akan berisi transisi nol ke semua keadaan akhir yang lama).

Ini akan membuat "membalikkan PDA" dari DPDA menjadi non-deterministik setiap kali ada lebih dari satu keadaan akhir tunggal dalam DPDA asli.

Apa kekeliruan dalam argumen saya? Atau adakah cara lain untuk membuktikan hal ini?

formal-languages context-free closure-properties pushdown-automata nondeterminism peteykun
sumber

Harap beri tahu saya jika jawaban StackOverflow saya memerlukan penjelasan tambahan. Masalah dengan upaya pembuktian Anda adalah ini: PDA yang Anda buat bukan satu-satunya PDA untuk bahasa yang diterimanya. Mungkin ada orang lain, mungkin tiba secara berbeda, yang bersifat deterministik. Secara khusus, DCFL dapat diterima oleh PDA yang tidak deterministik.

Patrick87

Benar, itulah sebabnya saya menyadari ini tidak banyak "bukti" sama sekali, itu hanya akan memiliki makna jika hasilnya selalu berupa DCFL, padahal sebenarnya tidak. Saya kira saya hanya mencoba untuk membuktikannya menggunakan metode yang sama seperti yang digunakan untuk bahasa Reguler dan gagal. Terima kasih atas contohnya!

peteykun

Mempertimbangkan

L = b^{n} c^{n} \cap a b^{2} n c^{n}

$L={b^n c^n} \cap {a b^2n c^n}$

Pranav

Tabel itu juga mengatakan bahasa rekursif ditutup

λ

$\lambda$ -pengganti bebas ... apakah itu benar?

anir

Jawaban:

Saya mencari Hopcroft dan Ullman 1979 dan mengatakan pada halaman 281 bahwa itu tidak ditutup dengan pembalikan. Tetapi saya tidak menemukan bukti dalam pandangan saya yang sangat cepat pada bab yang relevan.

Mencari di web juga memberikan jawaban negatif, dengan contoh balasan, pada stackoverflow oleh anggota CS (notasi disesuaikan):

$(a+b+c)^*WcW^R$ dimana $W \in (a+b)^+$ ; ini non-deterministik karena Anda tidak tahu di mana $WcW$ bit dimulai.

$W^RcW(a+b+c)^*$ dimana $W \in (a+b)^+$ ; ini deterministik karena Anda dapat menulis PDA deterministik untuk menerima palindrom sederhana dari formulir $W^RcW$ dan ubah status penerimaan untuk mengulang ke dirinya sendiri pada salah satu dari $a$ , $b$ dan $c$ .

Kuncinya di sini adalah bahwa PDA harus membaca input dari kiri ke kanan.

babou
sumber

Ini tidak masuk akal. Patrick87 memberikan contoh, @Raphael melakukan separuh pekerjaan pengeditan, dan saya mendapatkan perwakilannya. Kemudian, kita mendapat sangat sedikit untuk pekerjaan nyata ... :)

babou

Anggap saja sebagai "biaya finder" :) Saya hanya bingung sistem sebenarnya bekerja cukup baik sehingga Anda menemukan posting lama saya. Sistemnya bekerja! Salam SE!

Patrick87

Apakah H&U mengabaikan pembalikan untuk DCFL? Mereka menyebutkan non-penutupan di bawah penyatuan, penggabungan, Kleene, morfisme di Thm 10.5 lihat Latihan 10.4 (dibintangi tetapi dengan solusi). Namun, mereka mencatat

{0^{i} 1^{i} 2^{j} ∣ i, j} \cup {0^{i} 1^{j} 2^{j} ∣ i, j}

$\{ 0^i1^i2^j\mid i,j\} \cup \{ 0^i1^j2^j\mid i,j\}$ bukan DCFL, begitu juga tidak

K = {0^{i} 1^{i} 2^{j} a ∣ i, j} \cup {0^{i} 1^{j} 2^{j} b ∣ i, j}

$K = \{ 0^i1^i2^ja \mid i,j\} \cup \{ 0^i1^j2^jb\mid i,j\}$ dengan penutupan DCFL di bawah hasil bagi dengan set reguler, Thm 10.2. Namun pembalikan

K

$K$ adalah DCFL, 'penanda'

a

$a$ dan

b

$b$ berikan informasi ke mana harus menggunakan pushdown. [Mungkin @babou bisa menambahkan ini jika dia suka; dia yang mengumpulkan repetisi di sini :)]

Hendrik