Mesin Turing 1c2g3o

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