Mesin Turing
Pertemuan Ke-14 Sri Handayaningsih, S.T., M.T. Email :
[email protected] Teknik Informatika 1
TIU & TIK Memahami konsep : 1. Definisi Mesin Turing 2. Contoh aplikasi Mesin Turing 3. Mesin Turing sebagai penerima bahasa 4. Mesin Turing sebagai transducer
2
Hirarki Bahasa
n n n ? a b c
ww ?
Bahasa Bebas Konteks n n R
a b
ww
Bahasa Reguler
a*
a *b * 3
Bahasa yg diterima Mesin Turing
ww
n n n
a b c
Bahasa Bebas Konteks n n R
a b
ww
Bahasa Reguler
a*
a *b * 4
Definisi Formal untuk Mesin Turing
5
Fungsi Transisi
q1
a b, R
q2
( q1 , a) ( q2 , b, R )
6
Fungsi Transisi
q1
c d, L
q2
( q1 , c ) (q2 , d , L)
7
Definisi Mesin Turing:
States
Input alphabet
Pita alphabet
M (Q, , , , q0 , , F ) Fungsi Transisi State awal
State akhir kosong 8
Konfigurasi
c a b a q1
Diskripsi secara instan :
ca q1 ba
9
Time 4
Time 5
x a y b q2
Gerakan :
x a y b q0
q2 xayb x q0 ayb
10
Time 4
x a y b q2
Time 5
x a y b q0
Time 6
x x y b q1
Time 7
x x y b q1
q2 xayb x q0 ayb xx q1 yb xxy q1 b 11
q2 xayb x q0 ayb xx q1 yb xxy q1 b
Notasi yg Equivalen :
q2 xayb xxy q1 b
12
Initial configurasi:
q0 w
string Inputan
w a a b b q0 13
Bahasa yg Diterima Untuk setiap Mesin Turing M
L( M ) {w :
State awal
q0 w x1 q f x2} State akhir
14
Standar Mesin Turing Sebuah mesin dikatakan standar jika : • Deterministik • pita tak terhingga pada kedua arah •Pita merupakan input/output file
15
Tape ......
Mesin Turing ...... Read-Write head
Control Unit
16
Pita Tidak punya batasan – panjang tak terhingga ......
...... Read-Write head
head bergerak kiri atau kanan 17
......
...... Read-Write head
Langkah head pada setiap waktu : 1. Read (membaca) simbol 2. Write (menulis) simbol 3. Bergerak kiri atau kanan 18
Contoh :
Time 0
......
a b a c
Time 1
...... 1. Reads 2. Writes
a b k c
......
......
a k
3. Bergerak kiri 19
Time 1
......
a b k c
Time 2
...... 1. Reads 2. Writes
a f k c
......
......
b
f
3. Bergerak kanan 20
String inputan string Inputan ......
a b a c
Simbol kosong
......
head Head mulai pada posisi kiri pada string inputan 21
string Inputan ......
a b a c
Simbol kosong
......
head Catatan : string inputan tidak pernah kosong 22
State & Transisi Read
q1
q1
Write
a b, L
a b, R
Bergerak ke kiri (Left)
q2 Bergerak Kanan ( Right)
q2 23
Contoh : Time 1 ......
a b a c
......
q1
State saat ini
q1
a b, R
q2 24
......
Time 1
a b a c
......
......
q1 ......
Time 2
a b b c
q2 q1
a b, R
q2 25
Contoh : ......
Time 1
a b a c
......
......
q1 ......
Time 2
a b b c
q2 q1
a b, L
q2 26
Contoh : ......
Time 1
a b a c
......
q1 ......
Time 2
a b b c g
......
q2 q1
g, R
q2 27
Deterministik Mesin Turing adalah deterministik
Tdk diterima
diterima
a b, R
q2
a b, R
q2
a d, L
q3
q1
q1
b d, L
q3
Tidak ada transisi lambda yg mengikuti 28
Fungsi Transisi Parsial Contoh : ......
a b a c
......
q1
a b, R
q2
q1
b d, L
q3
Diterima : Tidak ada transisi untuk simbol inputan c 29
Menolak
Mesin akan menolak jika tidak ada transisi untuk diikuti
30
Contoh :
......
a b a c
......
q1
a b, R
q2
q1
b d, L
q3
Transisi tdk mungkin HALT !!! 31
State Akhir q1
q2
Diterima
q1
q2
Tdk diterima
•State akhir tdk mempunyai transisi keluar • pada state akhir mesin ditolak 32
Penerimaan Input diterima
Input ditolak
Jika mesin ditolak Pada state akhir
jika mesin halt pada state bukan akhir atau jika mesin pada loop Tak terhingga 33
Contoh MesinTuring Tentukan bahasa yg diterima oleh graf Transisi berikut ini ?
a a, R
q0
, L
q1 34
Jawaban Mesin Turing menerima bahasa :
aa *
a a, R
q0
, L
q1 35
Time 0
a a a q0
a a, R
q0
, L
q1 36
Time 1
a a a q0
a a, R
q0
, L
q1 37
Time 2
a a a q0
a a, R
q0
, L
q1 38
Time 3
a a a q0
a a, R
q0
, L
q1 39
Time 4
a a a
q1
a a, R
q0
Halt & diterima
, L
q1 40
Contoh yg ditolak Time 0
a b a q0
a a, R
q0
, L
q1 41
Time 1
a b a q0 Transisi tidak mungkin Halt & ditolak a a, R
q0
, L
q1 42
Tentukan bahasa yg diterima oleh graf Transisi berikut ini ?
b b, L a a, R
q0
, L
q1 43
Contoh Loop Tdk Berhenti Mesin Turing untuk bahasa
aa * b(a b) *
b b, L a a, R
q0
, L
q1 44
Time 0
a b a q0
b b, L a a, R
q0
, L
q1 45
Time 1
a b a q0
b b, L a a, R
q0
, L
q1 46
Time 2
a b a q0
b b, L a a, R
q0
, L
q1 47
Time 2
a b a
Time 3
a b a q0
Time 4
a b a q0
Time 5
a b a q0
Loop tidak berhenti
q0
48
kenapa loop tidak berhenti, karena: •State akhir tidak dapat direached •Mesin tidak pernah halts •inputan tidak diterima
49
Contoh Mesin Turing Lainya Tentukan bahasa yg diterima oleh graf Transisi berikut ini ?
y y, R
q3
q4 , L
y y, R
q0
y y, R a a, R
a x, R
q1
y y, L a a, L
b y, L
q2
x x, R 50
Jawaban : Mesin Turing untuk bahasa :
y y, R
q3
q4 , L
y y, R
q0
n n
{a b }
y y, R a a, R
a x, R
q1
y y, L a a, L
b y, L
q2
x x, R 51
a a b b
Time 0
q0
y y, R
q3
q4 , L
y y, R
q0
y y, R a a, R
a x, R
q1
y y, L a a, L
b y, L
q2
x x, R 52
x a b b
Time 1
q1
y y, R
q3
q4 , L
y y, R
q0
y y, R a a, R
a x, R
q1
y y, L a a, L
b y, L
q2
x x, R 53
x a b b
Time 2
q1
y y, R
q3
q4 , L
y y, R
q0
y y, R a a, R
a x, R
q1
y y, L a a, L
b y, L
q2
x x, R 54
x a y b
Time 3
q2
y y, R
q3
q4 , L
y y, R
q0
y y, R a a, R
a x, R
q1
y y, L a a, L
b y, L
q2
x x, R 55
x a y b
Time 4
q2
y y, R
q3
q4 , L
y y, R
q0
y y, R a a, R
a x, R
q1
y y, L a a, L
b y, L
q2
x x, R 56
x a y b
Time 5
q0
y y, R
q3
q4 , L
y y, R
q0
y y, R a a, R
a x, R
q1
y y, L a a, L
b y, L
q2
x x, R 57
x x y b
Time 6
q1
y y, R
q3
q4 , L
y y, R
q0
y y, R a a, R
a x, R
q1
y y, L a a, L
b y, L
q2
x x, R 58
x x y b
Time 7
q1
y y, R
q3
q4 , L
y y, R
q0
y y, R a a, R
a x, R
q1
y y, L a a, L
b y, L
q2
x x, R 59
x x y y
Time 8
q2
y y, R
q3
q4 , L
y y, R
q0
y y, R a a, R
a x, R
q1
y y, L a a, L
b y, L
q2
x x, R 60
x x y y
Time 9
q2
y y, R
q3
q4 , L
y y, R
q0
y y, R a a, R
a x, R
q1
y y, L a a, L
b y, L
q2
x x, R 61
x x y y
Time 10
q0
y y, R
q3
q4 , L
y y, R
q0
y y, R a a, R
a x, R
q1
y y, L a a, L
b y, L
q2
x x, R 62
x x y y
Time 11
q3
y y, R
q3
q4 , L
y y, R
q0
y y, R a a, R
a x, R
q1
y y, L a a, L
b y, L
q2
x x, R 63
x x y y
Time 12
q3
y y, R
q3
q4 , L
y y, R
q0
y y, R a a, R
a x, R
q1
y y, L a a, L
b y, L
q2
x x, R 64
x x y y
Time 13
q4 Halt & diterima
y y, R
q3
q4 , L
y y, R
q0
y y, R a a, R
a x, R
q1
y y, L a a, L
b y, L
q2
x x, R 65
Observasi: Jika dilakukan modifikasi pada n n Mesin untuk bahasa {a b }
Dengan sangat mudah untuk menkontruksi mesin untuk bahasa {a n b n c n } 66
Mesin untuk L = {vv|v in {a,b}*} ?
67
Fungsi Komputasi dengan Mesin Turing
68
fungsi
f (w) mempunyai:
Domain:
Range:
D
w D
f (w)
S
f ( w) S
69
Fungsi mungkin mempunyai banyak parameter :
Contoh:
Fungsi Penambahan
f ( x, y ) x y
70
Domain Integer Desimal:
0,5
Binary:
101
Unary:
11111
unary mudah utk dimanipulasi dengan mesin Turing 71
Definisi: fungsi f bisa dikomputasi jika MesinTuring M mempunyai hal-hal sbb : Configurasi awal
w
q0 State awal
Configurasi akhir
f (w) q f State akhir
Untuk semua w D Domain 72
Dengan kata lain : fungsi f bisa dikomputasi jika MesinTuring M mempunyai hal-hal sbb :
q0 w q f f ( w) Configurasi awal
Untuk semua
Configurasi akhir
w D
Domain 73
Contoh Fungsi
f ( x, y ) x y Dapat dikomputasi
x, y
integer
string Inputan : x0 y
unary
string Outputan : xy 0
unary
Mesin Turing:
74
x Mulai
1 1
y 1 0 1 1
q0 State awal “0” memrupakan pembatas Untuk dua nomer yang sama 75
y
x Start
1 1
1 0 1 1
q0 State awal
x y Finish
1 1
1 1 0
q f State akhir 76
‘0’ membantu ketika digunakan Sbg kesimpulan untuk operasi lain
x y Finish
1 1
1 1 0
q f State akhir 77
Mesin Turing untuk fungsi
1 1, R
f ( x, y ) x y
1 1, R
1 1, L
, L 0 1 , R q2 1 0, L q3 q0 q1 , R q4
78
Contoh eksekusi:
x 11
(2)
y 11 (2)
Time 0
y
x
1 1 0 1 1 q0 Kesimpulan akhir
x y
1 1 1 1 0 q4
79
Time 0
1 1 0 1 1 q0
1 1, R
1 1, R
1 1, L
, L 0 1 , R q2 1 0, L q3 q0 q1 , R q4
80
Time 1
1 1 0 1 1 q0
1 1, R
1 1, R
1 1, L
, L 0 1 , R q2 1 0, L q3 q0 q1 , R q4
81
Time 2
1 1 0 1 1 q0
1 1, R
1 1, R
1 1, L
, L 0 1 , R q2 1 0, L q3 q0 q1 , R q4
82
Time 3
1 1 1 1 1 q1
1 1, R
1 1, R
1 1, L
, L 0 1 , R q2 1 0, L q3 q0 q1 , R q4
83
Time 4
1 1 1 1 1 q1
1 1, R
1 1, R
1 1, L
, L 0 1 , R q2 1 0, L q3 q0 q1 , R q4
84
Time 5
1 1 1 1 1 q1
1 1, R
1 1, R
1 1, L
, L 0 1 , R q2 1 0, L q3 q0 q1 , R q4
85
Time 6
1 1 1 1 1 q2
1 1, R
1 1, R
1 1, L
, L 0 1 , R q2 1 0, L q3 q0 q1 , R q4
86
Time 7
1 1 1 1 0 q3
1 1, R
1 1, R
1 1, L
, L 0 1 , R q2 1 0, L q3 q0 q1 , R q4
87
Time 8
1 1 1 1 0 q3
1 1, R
1 1, R
1 1, L
, L 0 1 , R q2 1 0, L q3 q0 q1 , R q4
88
Time 9
1 1 1 1 0 q3
1 1, R
1 1, R
1 1, L
, L 0 1 , R q2 1 0, L q3 q0 q1 , R q4
89
Time 10
1 1 1 1 0 q3
1 1, R
1 1, R
1 1, L
, L 0 1 , R q2 1 0, L q3 q0 q1 , R q4
90
Time 11
1 1 1 1 0 q3
1 1, R
1 1, R
1 1, L
, L 0 1 , R q2 1 0, L q3 q0 q1 , R q4
91
Time 12
1 1 1 1 0 q4
1 1, R
1 1, R
1 1, L
, L 0 1 , R q2 1 0, L q3 q0 q1 HALT & diterima q4
, R 92
Pustaka 1. 2. 3. 4. 5. 6.
Tedy Setiadi, Diktat Teori Bahasa dan Otomata, Teknik Informatika UAD, 2005 Hopcroft John E., Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 2rd, Addison-Wesley,2000 Martin C. John, Introduction to Languages and Theory of Computation, McGraw-Hill Internatioanal edition,1991 Linz Peter,Introduction to Formal Languages & Automata, DC Heath and Company, 1990 Dulimarta Hans, Sudiana, Catatan Kuliah Matematika Informatika, Magister Teknik Informatika ITB, 1998 Hinrich Schütze, IMS, Uni Stuttgart, WS 2006/07, Slides based on RPI CSCI 2400
93
