Apakah otomat push-down dengan dua tumpukan setara dengan mesin turing?

41

Dalam jawaban ini disebutkan

Bahasa reguler dapat dikenali oleh otomat terbatas. Bahasa bebas konteks memerlukan tumpukan, dan bahasa sensitif konteks membutuhkan dua tumpukan (yang setara dengan mengatakan itu memerlukan mesin Turing penuh) .

Saya ingin tahu tentang kebenaran bagian yang berani di atas. Apakah itu benar atau tidak? Apa cara yang baik untuk mencapai jawaban ini?

computability turing-machines automata pushdown-automata Lazer
sumber
Ada dua klaim dalam teks tebal tetapi judul pertanyaan Anda menunjukkan bahwa Anda hanya tertarik pada salah satunya.
Tyson Williams
@TysonWilliams: ya, jadi?
Lazer
Ini membingungkan. Saya tidak tahu apa himpunan bagian dari kedua klaim yang Anda inginkan untuk dibenarkan.
Tyson Williams
Untuk yang tebal , seperti yang disebutkan dalam pertanyaan.
Lazer
2
@ Lazer: teks tebal berisi dua pernyataan ("CSL membutuhkan dua tumpukan", "dua tumpukan setara dengan TM"). Karena CSL adalah subset RE yang tepat, hanya satu yang benar.
Raphael

Jawaban:

38

Dua bit untuk jawaban ini;

Pertama, kelas bahasa yang dikenali oleh Turing Machines tidak peka terhadap konteks , tetapi bisa dihitung ulang secara berulang (peka konteks adalah kelas bahasa yang Anda dapatkan dari automata terikat linier ).

Bagian kedua, dengan asumsi kita menyesuaikan pertanyaan, adalah bahwa ya, PDA dua-stack sama kuatnya dengan TM. Agak lebih sederhana untuk mengasumsikan bahwa kita menggunakan model TM yang memiliki pita yang tak terbatas dalam satu arah saja (meskipun kedua arah tidak jauh lebih sulit, dan setara).

Untuk melihat kesetaraan, anggap tumpukan pertama sebagai isi kaset di sebelah kiri posisi saat ini, dan yang kedua sebagai isi di sebelah kanan. Anda memulai seperti ini:

  • Tekan spidol "bawah tumpukan" yang normal pada kedua tumpukan.
  • Dorong input ke tumpukan kiri (gunakan non-determinisme untuk "menebak" akhir input).
  • Pindahkan semuanya ke tumpukan yang tepat (untuk menjaga semuanya tetap dalam urutan yang tepat).

Sekarang Anda dapat mengabaikan input dan melakukan segalanya pada isi tumpukan (yang mensimulasikan rekaman itu). Anda muncul untuk membaca dan mendorong untuk menulis (sehingga Anda dapat mengubah "rekaman" dengan mendorong sesuatu yang berbeda dengan apa yang Anda baca). Kemudian kita dapat mensimulasikan TM dengan muncul dari tumpukan kanan dan mendorong ke kiri untuk bergerak ke kanan, dan sebaliknya untuk bergerak ke kiri. Jika kami menekan bagian bawah tumpukan kiri kami berperilaku sesuai (berhenti dan tolak, atau tetap di tempat Anda, tergantung pada model), jika kami menekan bagian bawah tumpukan kanan, kami hanya mendorong simbol kosong ke kiri.

Untuk bukti formal lengkap, lihat jawaban untuk pertanyaan lain .

Hubungan dengan cara lain harus lebih jelas, yaitu kita dapat mensimulasikan PDA dua-tumpukan dengan TM.

Luke Mathieson
sumber