tugas individu
Post on 11-Jan-2016
227 Views
Preview:
DESCRIPTION
TRANSCRIPT
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
top related