Nama : Ilyas Awaludin Jaelani

NIM : 005131121039

Mata Kuliah : Teori Bahasa dan Otomata

Tugas Individu

Natural Language / Mesin Turing

Unrestricted / Phase / Natural Language Adalah bahasa manusia atau bahasa alami termasuk

ke dalam grammar (tata bahasa) type 0 / unrestricted, di mana tidak ada batasan pada aturan

produksinya. Dalam bahasa Natural sebuah kalimat atau sentence dikatakan benar apabila

memenuhi aturan bahasa atau grammar yang ada dalam suatu bahasa.

Mesin Turing merupakan mesin yang merepresentasikan tata bahasa unrestricted.

Mesin Turing ini bersifat umum dan memiliki kemampuan yang lebih tinggi dari finite state

automata maupun push down automata dari segi aksi dan komponennya. Pada mesin Turing

memori akan berupa suatu pita yang pada dasarnya berupa array (deretan) sel-sel

penyimpanan. Setiap sel mampu menyimpan sebuah simbol tunggal.

Sebuah mesin Turing secara formal dinyatakan dalam 7 tupel M={ Q, Σ, Г, S, F, b,

δ }, dimana :

Q = himpunan state

Σ = kumpulan simbol input

Г = simbol dalam pita (meliputi juga blank)

S = state awal, S Q

F = himpunan state akhir

b = simbol kosong (blank), bukan bagian dari Σ

δ = fungsi transisi : Q X Г Q X Г X {R,L}

R = posisi baca/tulis bergerak kekanan (RIGHT)

L = posisi baca/tulis bergerak kekiri (LEFT)

Bagian pada pita yang belum ditulisi dianggap berisi simbol b.

Contoh Mesin Turing Sederhana

Kasus 1

Contoh: Q = {a, b, c, d, e}, = {0, 1, X, Y, B}, Σ = {0, 1, B}

q0 = a, F = {e}, dan fungsi transisi dinyatakan oleh tabel

1

berikut:

1

X Y B

maka komputasi string ‘0011’ oleh mesin Turing M

dinyatakan dalam rangkaian deskripsi sesaat berikut:

a0011 |-- Xb011 |-- X0b11 |-- Xc0Y1 |-- cX0Y1 |--

Xa0Y1 |-- XXbY1 |-- XXYa1 |-- XXcYY |-- XcXYY |--

XxaYY |-- XXYdY |-- XXYYd |-- XXYYBe (diterima)

Kasus 2

Tentukan bahasa yang dikenali oleh mesin turing berikut :

Mesin Turing dengan Q={q1,q2}, S={q1}, F={q2} dan δ berikut :

δ (q1,a)=(q1,a,R)

δ (q1, b) =(q2, b,R)

Jawab : uji dengan pemasukan :

b hasil q2

a hasil q2

aa hasil q2

aaa hasil q2

Kesimpulan :

Mesin tersebut menerima : b,a,aa,aaa,... atau {a*}

2