Bahasa yang Diterima & Bahasa yang Diputuskan

Sebuah TM menerima sebuah bahasa jika ia memasuki keadaan akhir untuk setiap input string w. Sebuah bahasa dapat dihitung secara rekursif (dihasilkan oleh tata bahasa Tipe-0) jika diterima oleh mesin Turing.

TM memutuskan suatu bahasa jika menerimanya dan masuk ke status menolak untuk input apa pun yang tidak ada dalam bahasa tersebut. Suatu bahasa bersifat rekursif jika diputuskan oleh mesin Turing.

Mungkin ada beberapa kasus di mana TM tidak berhenti. TM tersebut menerima bahasanya, tetapi tidak memutuskannya.

Merancang Mesin Turing

Panduan dasar mendesain mesin Turing telah dijelaskan di bawah ini dengan bantuan beberapa contoh.

Contoh 1

Rancang TM untuk mengenali semua string yang terdiri dari sejumlah ganjil α.

Solution

Mesin Turing M dapat dibangun dengan gerakan berikut -

Membiarkan q₁ menjadi keadaan awal.
Jika M masuk q₁; saat memindai α, ia memasuki statusq₂ dan menulis B (kosong).
Jika M masuk q₂; saat memindai α, ia memasuki statusq₁ dan menulis B (kosong).
Dari gerakan di atas, kita bisa melihat itu M memasuki negara bagian q₁ jika memindai bilangan genap α, dan memasuki status q₂jika memindai angka ganjil α. Karenanyaq₂ adalah satu-satunya negara penerima.

Karenanya,

M = {{q ₁ , q ₂ }, {1}, {1, B}, δ, q ₁ , B, {q ₂ }}

dimana δ diberikan oleh -

Simbol alfabet tape	Status Sekarang 'q ₁ '	Status Sekarang 'q ₂ '
α	BRq ₂	BRq ₁

Contoh 2

Rancang Mesin Turing yang membaca string yang mewakili bilangan biner dan menghapus semua 0 di depan dalam string. Namun, jika string hanya terdiri dari 0, itu membuat satu 0.

Solution

Mari kita asumsikan bahwa string input diakhiri oleh simbol kosong, B, di setiap ujung string.

Mesin Turing, M, dapat dibangun dengan gerakan berikut -

Membiarkan q₀ menjadi keadaan awal.
Jika M masuk q₀, saat membaca 0, bergerak ke kanan, memasuki status q₁ dan menghapus 0. Saat membaca 1, ia memasuki status q₂ dan bergerak ke kanan.
Jika M masuk q₁, saat membaca 0, ia bergerak ke kanan dan menghapus 0, yaitu, ia menggantikan 0 dengan B. Saat mencapai 1 paling kiri, ia masukq₂dan bergerak ke kanan. Jika mencapai B, yaitu, string hanya terdiri dari 0, ia bergerak ke kiri dan memasuki statusq₃.
Jika M masuk q₂, saat membaca 0 atau 1, bergerak ke kanan. Saat mencapai B, ia bergerak ke kiri dan memasuki keadaanq₄. Ini memvalidasi bahwa string hanya terdiri dari 0 dan 1.
Jika M masuk q₃, itu menggantikan B dengan 0, bergerak ke kiri dan mencapai keadaan akhir q_f.
Jika M masuk q₄, saat membaca 0 atau 1, bergerak ke kiri. Saat mencapai awal string, yaitu ketika membaca B, mencapai status akhirq_f.