Jika

9

Saya terjebak menyelesaikan latihan berikutnya:

Berargumen bahwa jika bebas konteks dan teratur, maka (yaitu hasil bagi yang tepat ) bebas konteks.R L / R = { w x RLRL/R={wxRs.twxL}

Saya tahu bahwa harus ada sebuah PDA yang menerima dan DFA yang menerima . Saya sekarang mencoba untuk menggabungkan automata ini ke PDA yang menerima hasil bagi yang tepat. Jika saya dapat membangunnya, saya membuktikan bahwa bebas konteks. Tapi saya terjebak membangun PDA ini.R L / RLRL/R

Sejauh ini saya sudah berhasil:

Dalam PDA gabungan negara-negara bagian adalah produk kartesius dari keadaan automata yang terpisah. Dan ujung-ujungnya adalah tepi DFA tetapi hanya tepi yang di masa depan keadaan akhir dari PDA asli L dapat dicapai. Tetapi tidak tahu bagaimana menuliskannya secara formal.

Dommicentl
sumber
Selamat datang! Di mana tepatnya Anda terjebak, apa pendekatan Anda?
Raphael
1
Petunjuk: pikirkan cara terbaik menggunakan non-determinisme.
Artem Kaznatcheev
Dalam PDA gabungan negara-negara bagian adalah produk kartesius dari keadaan automata yang terpisah. Dan ujung-ujungnya adalah tepi DFA tetapi hanya tepi yang di masa depan keadaan akhir dari PDA asli L dapat dicapai. Tetapi tidak tahu bagaimana cara memperbaikinya secara formal.
Dommicentl
3
Saya menyalin komentar Anda ke pertanyaan. Itu tempat yang lebih baik untuk itu.
Dave Clarke

Jawaban:

8

Ini sebuah petunjuk.

Anda perlu mesin Anda untuk awalnya menerima sebagian kata dari , sambil memakan kaset itu. Kemudian, tanpa mengkonsumsi apa pun, Anda perlu menemukan beberapa kata dari yang akan mendorong mesin ke keadaan akhir. Kata yang dipilih dari memainkan peran kata input untuk bagian kedua dari perhitungan.R RLRR

Jelas, non-determinisme akan berperan, seperti halnya produk antara kedua mesin. Trik dalam meresmikan ini adalah menyesuaikan produk untuk menghadapi kenyataan bahwa input berasal dari bukan dari input.R

Dave Clarke
sumber
6

Saya tidak yakin apa yang Anda maksud dengan produk kartesius; ini mensimulasikan kedua automata secara paralel, yang akan memberi Anda persimpangan. Tapi Anda ingin mengidentifikasi semua kata dalam yang memiliki akhiran dari ! Pada tingkat intuitif, itu.RLR

Asumsikan input kami adalah . Jelas, kami tidak dapat memeriksa semua kemungkinan lanjutan (untuk keanggotaan di ) tetapi hanya sejumlah yang terbatas. Komentar Artem sangat membantu di sini; kami menebak akhiran yang akan terjadi, dan menjalankan kedua automata di atasnya. R xwΣRx

Mari dan PDA untuk dan NFA untuk , masing-masing. Bangun otomat sebagai berikut. Pada input , simulasikan . Setelah dikonsumsi, beralih ke persimpangan dimodifikasi dari dan , menjaga negara dari . Sekarang, putuskan untuk setiap transisi nondeterministis simbol mana yang berikutnya dalam input virtual. Terima jika dan hanya jika kedua komponen mencapai keadaan akhir secara bersamaan, yaitu jikaA R L R A w Σ A L w A L , R A L A R A L w A L , R w x w x L x RALARLRAwΣALwAL,RALARALwAL,Rwmemiliki kelanjutan sehingga dan .xwxLxR

Anda juga dapat menggunakan tata bahasa formal. Apakah Anda melihat bagaimana Anda bisa mendapatkan dua tata bahasa secara paralel? Secara umum, tidak jelas bagaimana mengadaptasi sehingga Anda dapat menangani sufiks; menggunakan bentuk normal Chomsky membantu.GL

Asumsikan dan diberikan dalam bentuk normal Chomsky. Ubah sedemikian sehingga non-terminal paling kanan dapat dibedakan dan menjadikan simbol awal sebagai simbol awal baru. Perkenalkan untuk versi yang berbeda dari nonterminals aturan baru yang mengarah ke tata bahasa yang diturunkan dalam dan secara paralel (non-terminal adalah pasangan non-terminal); jika kedua tata bahasa menyetujui simbol terminal, hapus komposit non-terminal. Dengan cara itu, akhiran di dihapus jika dan hanya jika dapat diturunkan dalam dan di , tetap .G R G L G L G R G L G L G R w L / RGLGRGLGLGRGLGLGRwL/R

Raphael
sumber
Perhatikan bahwa apa yang ada di area spoiler tidak ketat atau formal. Tolong beri tahu saya jika Anda membutuhkan lebih banyak detail (setelah mencobanya sendiri).
Raphael
6

Saya merekomendasikan untuk menggunakan jawaban Raphael, yang jauh lebih mudah untuk dipahami, tetapi di sini ada satu alternatif, menggunakan properti penutupan daripada automata:

LAwLwxLxwwx

Lebih formal:

L(A×{0,1})L
(A×0)(R×1)× ( a , 0 ) a ( a , 1 ) εR×
(a,0)a(a,1)ε

Properti penutupan yang digunakan: Gambar homomorfik, preimage, persimpangan dengan bahasa biasa. Keuntungan: Bukti ini berfungsi untuk keluarga lain (misalnya, ganti bebas konteks dengan yang biasa).

sdcvvc
sumber
1
AL
Poin bagus.
sdcvvc
1
Secara teknis kelas semacam itu (tempat bukti ini bekerja) disebut kerucut atau trio penuh .
Hendrik Jan