Masalah apa pun yang dipecahkan oleh robot terbatas ada di P

8

Setelah kelas Teori Komputasi saya hari ini, pertanyaan ini muncul di benak saya: Jika masalah dapat diselesaikan oleh robot terbatas, masalah ini milik P.

Saya pikir itu benar, karena automata mengenali bahasa yang sangat sederhana, maka semua bahasa ini akan memiliki algoritma polinomial untuk menyelesaikannya. Jadi, apakah benar bahwa masalah yang diselesaikan oleh otomat terbatas ada di P?

Sisyphus
sumber

Jawaban:

15

Ya itu benar. Dalam hal kelas kompleksitas,

REGP,
dimana REGadalah kelas bahasa reguler (yaitu, masalah yang dapat dipecahkan oleh robot terbatas). Lebih spesifik,
(*)REGDTIME(n),
dan DTIME(n) adalah bagian ketat dari P oleh teorema hierarki waktu.

Bukti (*) adalah sebagai berikut: untuk masalah apa pun di REG, ada DFA yang menyelesaikannya. Ubah DFA menjadi mesin Turing dengan status dan fungsi transisi yang sama, yang selalu bergerak ke kanan hingga terlihat kosong, lalu menerima atau menolak. Mesin Turing ini selalu berhenti tepat waktun.


Perlu juga disebutkan

REG=DSPACE(0)=DSPACE(k)
untuk konstanta tetap k.
6005
sumber
7

Ya ini benar. Untuk setiap masalah seperti itu ada DFA yang memutuskan bahasa, dan memeriksa apakah sebuah kata diterima oleh DFA dapat dengan mudah dilakukan dalam waktu linier dalam panjang kata.

Pontus
sumber