Putuskan apakah bahasa bebas konteks dapat diterima oleh otomat pushdown deterministik

22

Diberi tata bahasa bebas konteks G, ada N Nondeterministic Pushdown Automaton yang menerima persis bahasa yang diterima G. (dan sebaliknya)

Ada mungkin juga ada sebuah deterministik Pushdown Automaton D yang menerima persis bahasa G menerima juga. Itu tergantung pada tata bahasanya.

Dengan algoritma apa pada produksi G kita dapat menentukan apakah D ada?

Andrew Tomazos
sumber
4
Bahkan jika Anda tahu sebelumnya bahwa ada DPDA untuk G, tidak ada algoritma untuk menemukannya. Lihat di sini .
sdcvvc

Jawaban:

20

Tidak ada algoritma yang memberikan tata bahasa bebas konteks, memutuskan apakah DPDA mengenali bahasa yang sama dan menghitungnya jika ada.

Karena jika algoritma semacam itu ada, kita akan dapat memutuskan masalah yang tidak dapat diputuskan dari universalitas tata bahasa bebas konteks yaitu apakah tata bahasa bebas konteks pada mengenali seluruh bahasa .GΣΣ

Misalkan ada algoritma . Biarkan menjadi beberapa tata bahasa bebas konteks. Biarkan menjadi . Kemudian algoritma akan memutuskan apakah ada DPDA mengakui .SEBUAHDPDSEBUAHGL.L.(G)SEBUAHDPDSEBUAHSEBUAHL.

  • Jika tidak ada DPDA seperti itu, maka tidak dikenali oleh DPDA, khususnya itu tidak teratur, sehingga tidak bisa .L.Σ

  • Jika DPDA ada maka kita dapat memutuskan apakah sama denganSEBUAHL.Σ karena universalitas dapat dipilih untuk DPDA. Mengapa? Karena:

    • Bahasa DPDA ditutup dengan pelengkap (karena DPDA bersifat deterministik)
    • kekosongan adalah decidable untuk DPDAs (karena itu untuk PDA )

Menggunakan kami telah membangun sebuah algoritma yang memutuskan apakah L ( G ) = Σ untuk tata bahasa G bebas konteks , yang telah terbukti tidak mungkin. Karenanya A D P D A tidak ada.SEBUAHDPDSEBUAHL(G)=ΣGADPDA

jmad
sumber
Saya tidak mengerti maaf ini. Apakah Anda menggunakan Σ untuk merujuk ke alfabet yang digunakan oleh G? Dan apa maksudmu "apakah L bahasa lengkapnya "? Apakah Anda mengatakan bahwa kami akan menjalankan algoritme pada tata bahasa G yang menghasilkan Σ , bahasa string apa saja di atas Σ? Kami jelas akan menemukan tidak hanya DPDA, tetapi DFA sederhana untuk bahasa ini. Pelengkap Σ adalah bahasa kosong, ini juga mudah dikenali oleh DPDA dan DFA - jadi saya jelas kehilangan sesuatu dalam penjelasan Anda. ΣΣΣ
Andrew Tomazos
Saya harap ini lebih jelas sekarang. Perhatikan bahwa saya menjawab pertanyaan yang sedikit berbeda: Saya bersumpah Anda bertanya apakah kami dapat menghitung , bukan hanya memutuskan apakah itu ada atau tidak. D
jmad