Pertemuan 14 Pengantar Ke Mesin Turing

7/30/2019 Pertemuan 14 Pengantar Ke Mesin Turing

1/27

Pertemuan 14Pengantar ke Mesin Turing

Teori Bahasa dan Otomata (KOM208)

SKS: 3(3-0)


2/27

TIK, Subtopik dan WaktuPenyajian

Tinjauan Instruksional Khusus : Mahasiswa akan dapat menjelaskan cara kerja mesin

turing. Subtopik :

Notasi untuk mesin turing Diagram transisi dari mesin turing Bahasa dari mesin turing

Waktu penyajian : 1 x 150 menit


3/27

Pendahuluan

Mesin Turing adalah model yang sangatsederhana dari komputer.

Secara esensial, mesin Turing adalah sebuahfinite automaton yang miliki sebuah tape tunggaldengan panjang tak terhingga yang dapatmembaca dan menulis data.

Mesin Turing menggunakan notasi seperti ID-IDpada PDA untuk menyatakan konfigurasi darikomputasinya.


4/27

Pendahuluan Stack pada PDA memiliki keterbatasan akses. Elemen yang dapat diakses hanya elemen yang ada

pada top stack . Pada Mesin Turing, memori akan berupa suatu tape

yang pada dasarnya merupakan array dari sel-selpenyimpanan.

Visualisasi dari sebuah mesin Turing diberikan olehgambar berikut:

B B X 1 X2 Xi Xn B B

FiniteControl


5/27

Pendahuluan

Mesin terdiri dari sebuah finite control , yangdapat berada dalam sebuah himpunanberhingga dari state .

Terdapat sebuah tape yang dibagi ke dalamkotak-kotak atau sel-sel. Setiap sel dapat menampung sebuah dari

sejumlah berhingga dari simbol.

Pada awalnya, input yang merupakan string darisimbol dengan panjang berhingga dipilih dariinput alphabet , ditempatkan pada tape .


6/27

Pendahuluan Sel-sel tape yang lain, perluasan secara infinite ke kiri

dan ke kanan, pada awalnya menampung simbol khususyang dinamakan blank .

Blank bukan sebuah input symbol , dan mungkin terdapatsimbol tape yang lain disamping input symbol dan blank .

Terdapat sebuah tape head yang selalu ditempatkanpada salah satu dari sel-sel tape .

Mesin turing dikatakan men- scan sel tersebut. Padaawalnya, tape head berada pada sel paling kiri yang

menampung input.


7/27

Pergerakan mesin Turing

Sebuah pergerakan mesin Turing adalahsebuah fungsi dari state dari finite control dantape symbol yang di- scan .

Dalam satu pergerakan, mesin Turing akan: Merubah state . Next state dapat sama dengancurrent state . Menulis sebuah tape symbol dalam sel yang di- scan .

Tape symbol ini mengganti symbol apapun yang adadalam sel tersebut. Secara opsional, simbol yangdituliskan dapat sama dengan simbol yang sekarangada dalam tape .

Memindahkan tape head ke kiri atau ke kanan.


8/27

Notasi formal Mesin Turing

Mesin Turing dijelaskan oleh 7- tuple :M = (Q, , , , q 0, B, F)

Komponen-komponennya adalah: Q: Himpunan berhingga dari state dari

finite control . : himpunan berhingga dari simbol-simbol

input. : Himpunan dari tape symbol .

merupakan subset dari .


9/27


: Fungsi transisi. Argumen (q, X)adalah sebuah state q dan sebuah tapesymbol X. Nilai dari (q, X), jika nilai

tersebut didefinisikan, adalah triple (p, Y,D), dimana: p adalah next state dalam Q Y adalah simbol, dalam , ditulis dalam sel yang

sedang di- scan , menggantikan simbol apapunyang ada dalam sel tersebut.

D adalah arah, berupa L atau R, berturut-turutmenyatakan left atau right , dan menyatakan arahdimana head bergerak.


10/27


q0: start state , sebuah anggota dari Q,dimana pada saat awal finite control ditemukan.

B: simbol blank . Simbol ini ada dalam tapi tidak dalam , yaitu B bukan sebuahsimbol input.

F: himpunan dari final state , subset dari Q.


11/27

Deskripsi Ins tantaneous (ID)untuk Mesin Turing

ID digunakan untuk mengetahui apa yang mesinTuring kerjakan. ID direpresentasikan olehstring X 1X2X3 Xi-1qX iXi+1 Xn, dimana: q adalah state dari TM Tape head men- scan simbol ke-i dari kiri. X1X2 Xn adalah bagian dari tape di antara nonblank

pada sel paling kiri dan paling kanan.

Pergerakan TM M = (Q, , , , q0, B, F)

dinyatakan oleh notasi atau . *M atau * digunakan untuk menunjukkan nol, satu ataulebih pergerakan dari TM.


12/27

ID untuk Mesin Turing

Anggap (q, X i) = (p, Y, L), yaitupergerakan selanjutnya adalah ke kiri.Maka

X1X2 Xi-1qX iXi+1 Xn X1X2 Xi-2pX i-1 YXi+1 Xn

Pergerakan ini menyatakan perubahan kestate p.

Tape head sekarang diposisikan di sel i-1.


13/27


Jika i = n dan Y = B maka simbol B yangditulis pada Xn berhubungan denganurutan tak hingga dari blank -blank yangmengikuti dan tidak muncul dalam IDselanjutnya. Dengan demikian

X1X2 ...Xn- 1 q Xn X1X2 Xn-2p Xn-1


14/27


Terdapat dua pengecualian: Jika i=1, maka M bergerak ke blank ke bagian

kiri dari X1. Dalam kasus ini,

qX1X2 ...X n pBYX2 Xn Jika i = n dan Y = B maka simbol B yang

ditulis pada Xn berhubungan dengan urutan

tak hingga dari blank -blank yang mengikutidan tidak muncul dalam ID selanjutnya.Dengan demikian

X1X

2...X

n-1q X

n X1X

2 Xn-2p X

n-1


15/27


Anggap (q, Xi) = (p, Y, R), yaitu pergerakanselanjutnya adalah ke kanan. MakaX1X2 Xi-1qX iXi+1 Xn X1X2 Xi-1 YpX i+1

Xn Tape head telah bergerak ke sel i+1. Terdapatdua pengecualian:

Jika i = n, maka sel ke-i+1 menampung sebuah blank ,dan sel tersebut bukan bagian dari ID sebelumnya.Dengan demikian

X1X2 ... X n-1 qXn X1 X2 Xn-1 YpB Jika i = 1 dan Y = B maka simbol B yang ditulis padaX1 berhubungan dengan urutan tak hingga dariblank -blank dan tidak muncul dalam ID selanjutnya.Dengan demikian

qX1X2 ...X n pX2 Xn


16/27

Contoh 1

Diberikan TM yang menerima bahasa {0 n1n |n 1}.M = ({q 0, q 1, q 2, q 3, q 4}, {0, 1},{0, 1, X, Y, B},

, q 0, B, {q 4})Fungsi transisi diberikan sebagai berikut:

State Simbol

0 1 X Y B

q0 (q1, X, R) - - (q3, Y, R) -

q1 (q1, 0, R) (q2, Y, L) - (q1, Y, R) -

q2 (q2, 0, L) - (q0, X, R) (q2, Y, L) -

q3 - - - (q3, Y, R) (q4, B, R)

q4 - - - - -


17/27

Contoh 1 (lanjutan)

Misalkan mesin Turing M diberi masukan0011. Pada keadaan awal, mesin TuringM berada dalam state q0, men- scan 0yang pertama, yaitu ID M awal adalahq00011.

Urutan pergerakan M adalah:q00011 Xq1011 X0q111 Xq20Y1 q2X0Y1 Xq00Y1 XXq1Y1 XXYq11 XXq2YY Xq2XYY XXq0YY XXYq3Y XXYYq 3B XXYYBq4B


18/27

Contoh 1 (lanjutan)

Contoh pergerakan yang lain diberikan input0010.

Urutan pergerakan M adalah:q00010 Xq1010 X0q110 Xq20Y0 q2X0Y0 Xq00Y0 XXq1Y0 XXYq10 XXY0q1B

Dalam state q1, M tidak memiliki pergerakan

pada tape symbol B. Dengan demikian M tidak menerima input yangdiberikan.


19/27

Diagram Transisi untuk MesinTuring

Diagram transisi terdiri dari sebuah himpunandari node -node yang menyatakan state -state dari Mesin Turing

sebuah arc dari state q ke state p diberi labeloleh satu atau lebih item dengan bentuk X/Y D,dimana X dan Y adalah tape symbol, dan Dadalah arah, kiri (L) atau kanan (R).

Bahwa bila (q, X) = (p, Y, D) diperoleh labelX/Y D pada arc dari q ke p.


20/27

Diagram Transisi untuk MesinTuring

Dalam diagram arah D dinyatakan dengantanda untuk left dan untuk right .

Start state ditandai dengan kata start dansebuah panah yang masuk ke dalam state tersebut.

Final state ditandai dengan putaranganda.


21/27

Diagram

transisiMesinTuring padaContoh 1:

q0 q1 q2

q3 q4

start0 / X

Y / Y0 / 0

Y / Y0 / 0

1 / Y

X / XY / Y

B / B

Y / Y


22/27

Contoh 2

Mesin Turing berikut menghitungan fungsi ,yang dinamakan monus atau proper substraction .

Fungsi ini didefinisikan oleh m n = max(m n,0). Bahwa, m n = m n jika m n dan 0 jika m< n.

Mesin Turing yang melakukan operasi ini adalahM = ({q 0, q 1, ... , q 6}, {0, 1}, {0, 1, B}, , q 0, B)


23/27

Aturan untuk fungsi transisi :

State Simbol 0 1 B

q0 (q1, B, R) (q5, B, R) - q1 (q1, 0, R) (q2, 1, R) - q2 (q3, 1, L) (q2, 1, R) (q4, B, L) q3 (q3, 0, L) (q3, 1, L) (q0, B, R) q4 (q4, 0, L) (q4, B, L) (q6, 0, R) q5 (q5, B, R) (q5, B, R) (q6, B, R) q6 - - -


24/27

Diagram transisi dari mesin TuringM:

q0 q1 q2 q3

q5 q6 q4

start 0/ B

0/ 0

1/ 1

1/ 1

B/ B

0/ 1

0/ 01/ 1

B/ B1/ B

B/ B B/ 0

0/ B1/ B

0/ 01/ B


25/27

Bahasa dari Mesin Turing,Mesin Turing dan Halt ing

Misalkan M = (Q, , , , q0, B, F) adalah mesin Turing.Maka L(M) adalah himpunan dari string-string w dalam

* sedemikian sehingga q0w p untuk suatu state pdalam F dan string tape dan .

Mesin Turing dan Halt ing: Notasi acceptance lain yang sering digunakan dalam

mesin Turing adalah acceptance by halting .

Mesin Turing dikatakan halt jika mesin tersebut masukke sebuah state q, men- scan simbol tape X, dan tidakada pergerakan dalam kasus ini; yaitu (q, X) tidakdidefinisikan.


26/27

Contoh 3

Mesin Turing dalam Contoh 2 tidak dirancanguntuk menerima sebuah bahasa, tetapi sebagaikomputasi fungsi aritmatika.

Perhatikan bahwa M halt pada semua string daripara 0 dan para 1, karena apapun yangditemukan M pada tape -nya, M akan menggantikelompok kedua dari para 0 Jika m dapat menemukan grup tersebut, berlawanan

dengan grup pertama dari para 0, dan dengandemikian M mencapai state q6 dan halt .


27/27

Daftar Pustaka

John E. Hopcroft, Rajeev Motwani, JeffreyD. Ullman. 2001. Introduction to AutomataTheory, Languange, and Computation .Edisi ke-2. Addison-Wesley

Pertemuan 14 Pengantar Ke Mesin Turing

Documents