Apakah dapat diputuskan apakah otomat pushdown mengenali bahasa reguler yang diberikan?

Masalah apakah dua automat pushdown mengenali bahasa yang sama tidak dapat diputuskan. Masalah apakah automat pushdown mengenali bahasa kosong dapat diputuskan, maka itu juga dapat memutuskan apakah ia mengenali bahasa yang terbatas. Tidak dapat diputuskan apakah bahasa yang diterima oleh otomat pushdown adalah biasa. Tapi ...

... apakah dapat diputuskan apakah otomat pushdown mengenali bahasa reguler yang diberikan ?

Jika jawabannya tidak, apakah masalahnya menjadi decidable jika bahasa reguler yang diberikan memiliki tinggi bintang $1$ ?

Tidak dapat dipastikan apakah PDA mengenali , himpunan semua string di atas alfabet input.$\Sigma^*$

Ditambahkan. Tidak dapat dipastikan untuk memeriksa bahwa sebagai konsekuensi dari kenyataan bahwa perhitungan "tidak valid" dari TM dapat dikodekan sebagai string CFG. Ini adalah Lemma 8.7 dari Pengantar Teori Automata oleh Hopcroft dan Ullman. Penulis merujuk untuk hasil ini ke Hartmanis (1967), bahasa bebas konteks dan perhitungan mesin Turing.$L(G)=\Sigma^*$

Pengkodean yang mudah dari perhitungan mesin Turing adalah sebagai berikut. Sebuah konfigurasi TM M adalah string dari bentuk x p y mana u v adalah isi rekaman itu, dan negara p ditunjukkan pada posisi di mana bertempat tinggal kepala. Penting untuk dicatat bahwa langkah-langkah komputasi TM adalah perubahan lokal : u c p a v ⊢ u q c b v untuk instruksi ( p , a , q , b , $M$$M$$xpy$$uv$$p$$ucpav \vdash uqcbv$ mana kepala bergerak ke kiri, dan u c p a v ⊢ u c b q v untuk instruksi ( p , a , q , b , R ) di mana kepala bergerak ke kanan.$(p,a,q,b,L)$$ucpav \vdash ucbqv$$(p,a,q,b,R)$

Perhitungan yang valid dapat dikodekan sebagai string mana w 0 = q 0 x kode konfigurasi awal pada string x , dan kami memiliki langkah-langkah yang tepat w i ⊢ w i + 1 . Konfigurasi terakhir dalam string harus final, yaitu memiliki keadaan terputus-putus.$w_0\#w_1^R\#w_2\#w_3^R\# \dots$$w_0 = q_0x$$x$$w_i \vdash w_{i+1}$

Sekarang merupakan latihan untuk memverifikasi bahwa string yang bukan perhitungan yang valid dapat dihasilkan oleh CFG (atau diterima oleh PDA). String yang tidak terdiri dari urutan konfigurasi bahkan teratur. Jika tidak satu non-deterministik menebak posisi di mana tidak w i ⊢ w i + 1 . Bagian dari string ini dihasilkan oleh tata bahasa yang mirip dengan satu untuk { x # y R ∣ x , y ∈ { a , b } ∗ , x ≠ y } .$G_M$ $w_i \vdash w_{i+1}$$\{ x\#y^R \mid x,y\in \{a,b\}^* , x\neq y\}$

Jika TM tidak memiliki string yang diterima, itu tidak akan memiliki perhitungan yang valid, dan semua string yang dihasilkan oleh tata bahasa G M .$M$$G_M$