UAS Pengantar Bahasa dan Otomata

UAS Pengantar Bahasa dan Otomata

(SUDANA NASRUDIN/161021450197/ERESHA/05TPLE003)

Assallamuallaikum wr.wb

Kali ini saya akan memaparkan beberaapa tugas Pengantar Bahasa dan Otomata yang mesin moore

Mesin Moore

Suatu keterbatasan  dari finite state automata yang sudah kita pelajari selama ini keputusannya  terbatas pada diterima atau ditolak. otomata tersebut biasa disebut sebagai accepter, dalam hal ini finite state accepter. Kita bisa mengkonstruksi  sebuah finite state automata yang memiliki keputusan beberapa keluaran/output,  dalam hal ini otomata  tersebut  akan dikenal  sebagai  transducer.  Pada  mesin  Moore,  output akan berasosiasi dengan state. Mesin Moore didefinisikan dalam 6 (enam) tupel, M = (Q, S,

d, S, ∆,λ), dimana:

Q = himpunan state

∑ = himpunan symbol input

δ= fungsi transisi

S = state awal, S∈ Q

∆ = himpunan output

λ= fungsi output untuk setiap state

*Perhatikan:  komponen  state  Final  dari  Deterministic  Finite  Automata  dihilangkan, karena disini keputusan dimunculkan sebagai output.

Kita lihat contoh penerapan dari Mesin Moore. Misal kita ingin memperoleh sisa pembagian (modulus) suatu bilangan dengan 6. Dimana input dinyatakan dalam biner. Mesin Moore yang bersesuaian bisa dilihat pada gambar yg diatas. Konfigurasi mesin sebagai berikut:

Q = {q0,q1,q2,q3,q4,q5}

∑ =  {0,1} (input dalam biner)

∆ = {0,1,2,3,4,5}  (untuk output-nya pada kasus mod dengan 6 maka sisanya kemungkinan adalah (0,1,2,3,4,5)

S = q0

λ (q0) = 0

λ (q1) =1

λ (q2) =2

λ (q3) =3

λ (q4) =4

λ (q5) =5

δ	0	1
Q0	Q0	Q1
Q1	Q2	Q3
Q2	Q4	Q5
Q3	Q0	Q1
Q4	Q2	Q3
Q5	Q4	Q5

Misalkan saja

Decimal	mod	sisa bagi	binary
7	6	1	1
8	6	2	10
9	6	3	11
10	6	4	100
11	6	5	101
12	6	0	0
13	6	1	1
14	6	2	10

Hasil test step by state Run

Berikut hasil running awal yang saya input.

Add caption