Tunjukkan bahwa DPDA ditutup dengan konstruksi

Saya telah mencoba cukup lama untuk menemukan konstruksi sehingga saya dapat secara resmi menunjukkan bahwa PDA deterministik ditutup dengan komplementasi. Namun, kebetulan setiap ide yang saya dapatkan memiliki sesuatu yang pada akhirnya tidak cocok. Bisakah Anda membantu saya?

Masalah utama terjadi dengan ε-move . PDA dapat selesai membaca inputnya dalam keadaan non-final (menolak) tetapi masih dapat pindah ke status final (menerima) melalui ε-move dan akhirnya menerima string. Ini berarti bahwa menambahkan status mati dan melengkapi status tidak berfungsi. Saya sudah memecahkan masalah kemungkinan urutan tak terbatas dari ε-move , jadi itu bukan bagian utama dari pertanyaan saya.

EDIT: Sejauh yang saya mengerti, jika DPDA mencapai akhir input dan berada dalam keadaan menerima dan pindah ke keadaan menolak melalui ε-pindah itu masih akan menerimanya (karena mencapai keadaan akhir tanpa simbol input tersisa untuk Baca).

Tolong beri tahu saya jika saya bisa lebih jelas.

Saya tidak punya waktu untuk menulis ini sebelumnya tetapi saya menemukan jawaban. Inilah yang saya lakukan:

Membiarkan $O$ menjadi yang asli $PDA$. Kami akan membangun yang baru$PDA$, panggil saja $M$ ($M$ singkatan dimodifikasi).

Untuk menemukan pelengkap dari $O$, kita dapat membalik status akhir menjadi status non-final dan sebaliknya. Ini adalah prosedur yang sama seperti untuk automatas terbatas. Namun, ada kehalusan. Masalah utama adalah bahwa dalam PDA asli$O$ input $w$ dapat menyebabkan suatu negara $S$ yang bukan merupakan kondisi akhir tetapi bisa melakukan $\epsilon-move$ dan sampai ke negara penerima $S'$. Membalik keadaan seperti yang disebutkan di atas, akan membuat$M$ diakhiri $S$ dengan input $w$ yang akan menjadi kondisi akhir (menyebabkan $M$ menerima menerima input) meskipun nantinya akan menghasilkan $\epsilon-move$ untuk $S'$, negara yang tidak menerima. Karena itu keduanya$O$ dan $M$ akan menerima $w$. Hal serupa terjadi jika$S$ adalah kondisi terakhir dan $S'$ negara non-final yang dapat dijangkau dari $S$ melalui sebuah $\epsilon-move$.

Untuk mengatasi masalah ini, kita harus memastikan itu semua $\epsilon$-pindah terjadi sebelum kita membaca simbol berikutnya. Artinya, kita akan memasuki kondisi membaca hanya ketika jalur$\epsilon$-pindah diikuti dan kami mencapai negara yang tidak memiliki $\epsilon$-Pindah tersedia. Kami menyebut negara bagian terakhir ini sebagai negara bagian pembacaan , karena mereka memerlukan simbol aktual untuk melakukan transisi baru.

Menetapkan $M$Menyatakan menjadi tupel dari formulir $<q, n>$ dimana $q \in Q$ ($Q$ adalah himpunan negara asli $PDA$) dan $n \in \{1, 2, 3, 4\}$.

• Jika $\delta(q, \epsilon, X) = <q', \alpha>$ di $O$biarkan $\delta(<q, 3>, \epsilon, X) = <<q', 2>, \alpha>$ di $M$ jika $q \in F_O$.

• Jika $\delta(q, \epsilon, X) = <q', \alpha>$ di $O$biarkan $\delta(<q, 3>, \epsilon, X) = <<q', 3>, \alpha>$ di $M$ jika $q \notin F_O$.

• Jika $\delta(q, \epsilon, X) = <q', \alpha>$ di $O$biarkan $\delta(<q, 2>, \epsilon, X) = <<q', 2>, \alpha>$ di $M$.

• Jika $\delta(q, \epsilon, X)$ adalah $undefined$ di $O$, $\delta(<q, 2>, \epsilon, X) = <<q, 1>, X>$ di $M$

• Jika $\delta(q, \epsilon, X)$ adalah $undefined$ di $O$, $\delta(<q, 3>, \epsilon, X) = <<q, 4>, X>$ di $M$

Dalam definisi-definisi itu, kita membiarkan keadaan bentuk $<q, 2>$ dan $<q, 3>$ mengkonsumsi $\epsilon$-pindah meniru $\epsilon$-pindah dari $O$sampai tidak ada lagi. Kemudian, lakukan$\epsilon$-Pindah ke kondisi membaca. Sekarang untuk kondisi membaca,

• Jika $\delta(q, a, X) = <q', \alpha>$ di $O$biarkan $\delta(<q, 1>, a, X) = \delta(<q, 4>, a, X) = <<q', 3>, \alpha>$ di $M$.

Dengan membuat definisi ini, kita mengkonsumsi simbol input dan pindah ke keadaan form $<q, 3>$ untuk memulai seri baru $\epsilon$-pindah.

Akhirnya, buat status formulir $<q, 4>$ menjadi negara penerima $M$ jika $q \notin F_O$. Juga, buat$<q_0, 3>$ keadaan awal dari $M$ jika $q_0$ adalah kondisi awal dari $O$.

Apa yang kami lakukan adalah sebagai berikut:

Buat 4 "lantai" negara (elemen kedua tuple di negara bagian $M$menentukan di lantai berapa kita berada). Lantai 3 meniru$\epsilon$-pindah dari $O$ mungkin mencapai negara penerima $q$ dari $O$. Jika itu masalahnya, kami pindah ke lantai 2; kalau tidak, kita tetap di lantai 3. Ketika tidak ada lagi$\epsilon$-Pindah yang harus diikuti $O$, kami mendefinisikan $\epsilon$-pindah dari $M$untuk mencapai kondisi membaca. Lantai 1 dan 4 sesuai dengan status membaca. Jika kita berada di lantai 3, kita pergi ke lantai 4. Jika kita berada di lantai 2, kita mencapai lantai 1. Hanya negara$<q, 4>$ (Status yang ada di lantai 4) menerima status dari $M$, dengan ketentuan $q$ bukan kondisi penerimaan $O$.

Tolong beri tahu saya jika saya membuat kesalahan ketik saat menulis ini. Saya bisa dengan mudah keliru. Juga, bahasa Inggris saya tidak begitu baik sehingga merasa bebas untuk mengedit dan menyusun ulang hal-hal yang lebih baik.

Ada bukti oleh konstruksi dalam Pengantar Sipser untuk Teori Komputasi (3$^{rd}$edisi memiliki bagian tentang DCFL) yang mengidentifikasi status membaca automaton dengan membagi setiap negara yang membaca dan muncul sekaligus. Hanya status membaca ini yang bisa menjadi status akhir, dan untuk mendapatkan DPDA pelengkap Anda hanya membalikkan perilaku penerimaan dalam set status membaca.

Anda dapat mengasumsikan otomat bebas dari $\varepsilon$-transisi tanpa kehilangan generalitas.

Ini dapat ditunjukkan dengan menggunakan konstruksi standar dari CFG ke PDA yang diterapkan pada bentuk normal Greibach . Dalam Silent Transitions in Automata with Storage , G. Zetzsche baru-baru ini mempresentasikan konstruksi langsung pada automata.

Peringatan potensial: Saya agak berasumsi bahwa konstruksi standar menghasilkan DPDA jika kita menerapkannya pada tata bahasa yang sesuai, yaitu "deterministik", dan bahwa kesesuaian ini bertahan dari transformasi dalam bentuk normal Greibach.