Kita dapat membuat suatu finite state automata dengan beberapa keluaran/output, yang disebut ?

Download presentation

Finite State Automata (FSA) Dengan Output Pertemuan 7

7. 1. Mesin Moore �Suatu keterbatasan dari FSA yang sudah dipelajari sebelumnya adalah: keputusannya terbatas pada diterima atau ditolak. Otomata tsb biasa disebut dengan accepter (dalam hal ini FSA). �Kita dapat mengkonstruksi sebuah FSA yang memiliki keputusan beberapa keluaran (output), dalam hal ini otomata tersebut dikenal sebagai transducer. �Pada mesin Moore, output akan berasosiasi dengan state.

Mesin Moore didefinisikan dalam 6 tupel, yaitu: M=(Q, , , S, , ) Dimana: Q S = = = himpunan state himpunan simbol input fungsi transisi state awal, dimana S Q himpunan output fungsi output untuk setiap output

Contoh Mesin Moore Misalnya kita ingin memperoleh sisa pembagian (modulus) suatu bilangan dengan 3, dimana input dinyatakan dengan biner. Konfigurasi mesinnya adalah sbb: Q = {q 0, q 1, q 2} = {0, 1} S = q 0 = {0, 1, 2} untuk output pada kasus mod dengan 3, kemungkinan sisa pembagiannya adalah 1, 2 atau 3 = q 0=0, q 1=1, q 2=2

0 q 0 0 1 1 1 q 1 1 0 0 q 2 2 Gambar 7. 1. Mesin Moore untuk MOD 3 Coba buktikan untuk: • 5 MOD 3. • 10 MOD 3 (Input nya harus dirubah dulu kedalam biner)

7. 2. Mesin Mealy �Bila output pada mesin Moore berasosiasi dengan state, maka output pada mesin Mealy akan berasosiasi dengan transisi. �Mesin Mealy sendiri didefinisikandalam 6 tupel, yaitu: M=(Q, , , S, , ) Dimana: Q = himpunan state = himpunan simbol input = fungsi transisi S = state awal, dimana S Q = himpunan output = fungsi output untuk setiap output

Contoh Mesin Mealy Mesin ini akan mengeluarkan output menerima ‘Y’ atau menolak ’T’ suatu masukan biner. Dengan ketentuan: mesin akan mengeluarkan output ‘Y’ bila menerima untai yang memiliki dua simbol berurutan yang sama, atau secara formal dalam ER: (0+1)*(00+11) Konfigurasi mesinnya adalah sbb: Q = {q 0, q 1, q 2} = {0, 1}, 0 S = q 0 = {Y, T} (q 0, 0)=T; (q 0, 1)=T; (q 1, 0)=Y; (q 1, 1)=T (q 2, 0)=T; (q 2, 1)=Y

0/Y 0/T q 0 1/T q 1 0/T 1/T q 2 1/Y Gambar 7. 2. Contoh Mesin Mealy Coba buktikan untuk input yang diterima: 01011; 01100; 1010100; 10110100; 11; 100; 011; 111; 0101; 0010

7. 3. Ekuivalensi Mesin Moore dan Mesin Mealy �Dari suatu mesi Moore, dapat dibuat mesin Mealy yang ekuivalen, begitu juga sebaliknya. �State pada mesin Moore dibentuk dari kombinasi state pada Mealy dan banyaknya output. �Untuk mesin Mealy pada gambar 7. 2, jumlah state=3; dan jumlah output=2; maka jumlah state pada mesin Moore yang ekuivalen adalah = 6. �Konfigurasi mes. In Moore yang dibentuk adalah: Q = {q 0 Y, q 0 T, q 1 Y, q 1 T, q 2 Y, q 2 T} = {0, 1} S = q 0 = {0, 1, 2} (q 0 Y)=Y; (q 0 T)=T; (q 1 Y)=Y; (q 1 T)=T; (q 2 Y)=Y; (q 2 T)=T

1 1 0 q 0 T T q 0 T Y 0 0 0 q 0 T T T 1 0 q 0 T Y 1 1 Gambar 7. 3. Mesin Moore yang ekuivalen dengan Mesin Mealy pada gambar 7. 2.

�Untuk memperoleh ekuivalensi mesin Mealy dari suatu mesin Moore, caranya lebih mudah, cukup dengan menambahkan label output ke setiap transisi, dan menghapus label output pada setiap state �Konfigurasi mes. In Moore yang dibentuk adalah: Q = {q 0, q 1, q 2} = {0, 1} S = q 0 = {0, 1, 2} (q 0, 0)=0; (q 0, 1)=1 (q 1, 0)=2; (q 1, 1)=0 (q 2, 0)=1; (q 2, 1)=3

0/0 q 0 1/2 1/1 1/0 q 1 0/2 q 2 0/1 Gambar 7. 4. Mesin Mealy yang ekuivalen dengan Mesin Moore pada gambar 7. 1.

Latihan Soal

1. Suatu FSA, dimana keputusannya terbatas pada diterima atu ditolak, disebut dengan: a. accepter d. transducer b. receiver e. mesin Mealy c. mesin Moore 2. Suatu FSA, dimana output berasosiasi dengan state adalah: a. accepter d. transducer b. receiver e. mesin Mealy c. mesin Moore

2. Suatu FSA, dimana output berasosiasi dengan state adalah: a. accepter d. transducer b. receiver e. mesin Mealy c. mesin Moore 3. Mesin Moore didefininisikan dalam enam tupel: M=(Q, , , S, , ). Yang merupakan himpunan input adalah: a. d. b. e. c. S

3. Mesin Moore didefininisikan dalam enam tupel: M=(Q, , , S, , ). Yang merupakan himpunan input adalah: a. d. b. e. c. S 4. Suatu FSA, dimana output berasosiasi dengan transisi adalah: a. accepter d. transducer b. receiver e. mesin Mealy c. mesin Moore

4. Suatu FSA, dimana output berasosiasi dengan transisi adalah: a. accepter d. transducer b. receiver e. mesin Mealy c. mesin Moore 5. Suatu mesin Mealy memiliki 3 state dan 2 output, maka mesin Moore yang ekivalen dengan mesin Mealy tersebut memiliki state sebanyak: a. 8 d. 6 b. 10 e. 7 c. 5

5. Suatu mesin Mealy memiliki 3 state dan 2 output, maka mesin Moore yang ekivalen dengan mesin Mealy tersebut memiliki state sebanyak: a. 8 d. 6 b. 10 e. 7 c. 5 1. Suatu FSA, dimana keputusannya terbatas pada diterima atu ditolak, disebut dengan: a. accepter d. transducer b. receiver e. mesin Mealy c. mesin Moore