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 q1 menjadi keadaan awal.

  • Jika M masuk q1; saat memindai α, ia memasuki statusq2 dan menulis B (kosong).

  • Jika M masuk q2; saat memindai α, ia memasuki statusq1 dan menulis B (kosong).

  • Dari gerakan di atas, kita bisa melihat itu M memasuki negara bagian q1 jika memindai bilangan genap α, dan memasuki status q2jika memindai angka ganjil α. Karenanyaq2 adalah satu-satunya negara penerima.

Karenanya,

M = {{q 1 , q 2 }, {1}, {1, B}, δ, q 1 , B, {q 2 }}

dimana δ diberikan oleh -

Simbol alfabet tape Status Sekarang 'q 1 ' Status Sekarang 'q 2 '
α BRq 2 BRq 1

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 q0 menjadi keadaan awal.

  • Jika M masuk q0, saat membaca 0, bergerak ke kanan, memasuki status q1 dan menghapus 0. Saat membaca 1, ia memasuki status q2 dan bergerak ke kanan.

  • Jika M masuk q1, saat membaca 0, ia bergerak ke kanan dan menghapus 0, yaitu, ia menggantikan 0 dengan B. Saat mencapai 1 paling kiri, ia masukq2dan bergerak ke kanan. Jika mencapai B, yaitu, string hanya terdiri dari 0, ia bergerak ke kiri dan memasuki statusq3.

  • Jika M masuk q2, saat membaca 0 atau 1, bergerak ke kanan. Saat mencapai B, ia bergerak ke kiri dan memasuki keadaanq4. Ini memvalidasi bahwa string hanya terdiri dari 0 dan 1.

  • Jika M masuk q3, itu menggantikan B dengan 0, bergerak ke kiri dan mencapai keadaan akhir qf.

  • Jika M masuk q4, saat membaca 0 atau 1, bergerak ke kiri. Saat mencapai awal string, yaitu ketika membaca B, mencapai status akhirqf.

Karenanya,

M = {{q 0 , q 1 , q 2 , q 3 , q 4 , q f }, {0,1, B}, {1, B}, δ, q 0 , B, {q f }}

dimana δ diberikan oleh -

Simbol alfabet tape Status Sekarang 'q 0 ' Status Sekarang 'q 1 ' Status Sekarang 'q 2 ' Status Sekarang 'q 3 ' Status Sekarang 'q 4 '
0 BRq 1 BRq 1 ORq 2 - OLq 4
1 1Rq 2 1Rq 2 1Rq 2 - 1Lq 4
B BRq 1 BLq 3 BLq 4 OLq f BRq f