![Finite State Transducer (FST) [PDF]](https://pdfs.asia/img/200x200/finite-state-transducer-fst.jpg)
16 0 1 MB
Input Deretan karakter atau string Ouput Diterima atau tidak diterimanya suatu inputan
Kita dapat membuat suatu Finite State Automata dengan beberapa keluaran/output. Automata ini disebut Finite State Transducer
Input Deretan karakter atau string Ouput Penerjemahan string inputan menjadi string output. Output dapat berada pada setiap state atau label transisi
Mealy Machine Moore Machine
FST terdiri dari sejumlah state tanpa final state State tersebut dihubungkan oleh transisi yang diberi label pasangan input / output (Mealy Machine) Output berasosiasi dengan state (Moore Machine) FST dimulai dalam keadaan awal yang ditentukan dan melompat ke keadaan yang berbeda tergantung pada masukan, sambil menghasilkan keluaran sesuai dengan tabel transisinya.
Pada mesin moore, output akan berasosiasi dengan state. Didefinisikan dengan 6 tupel :
Q Himpunan state Σ Himpunan simbol input δ Fungsi Transisi S State awal Δ Himpunan output λ Fungsi Output untuk setiap state
Contoh 1 : Mesin moore untuk mencari komplemen dari nilai biner yang diinputkan.
Contoh 1 :
Contoh 1 : Inputan 1011 Input
1 0 1 1
Output State
Contoh 1 : Inputan 0110 Input
0 1 1 0
Output State
Contoh 2 : Memperoleh sisa pembagian (modulus) suatu bilangan dengan 3.
Contoh 2 :
Contoh 2 : 5 Mod 3 = ? 5 Dalam biner = 101 Input
1 0 1
Output State
Contoh 2 : 7 Mod 3 = ? 7 Dalam biner = 111 Input
1 1 1
Output State
Contoh 2 : 6 Mod 3 = ? 6 Dalam biner = 110 Input
1 1 0
Output State
Contoh 3 : Berapa kali deret string “abb” muncul dalam sebuah inputan string
Contoh 3 : Berapa kali deret string “abb” muncul dalam sebuah inputan string
Contoh 3 :
Contoh 3 : Inputan babbabb Input
b a b b a b b
Output State
Contoh 3 : Inputan abaaabb Input
a b a a a b b
Output State
Contoh 3 : Inputan abaabab Input
a b a a b a b
Output State
Pada mesin mealy, output akan berasosiasi dengan transisi. Didefinisikan dengan 6 tupel :
Q Himpunan state Σ Himpunan simbol input δ Fungsi Transisi S State awal Δ Himpunan output λ Fungsi Output untuk setiap transisi
Contoh 4 : Terdapat suatu mesin mealy yang menghasilkan output berdasarkan suatu masukan. Mesin ini mengeluarkan output Y(“Ya”) apabila menerima untai yang memiliki akhiran simbol berurutan yang sama dan output T (“tidak”) jika sebaliknya. δ δ(q0,0) = δ(q0,1) = δ(q1,0) = δ(q1,1) = δ(q2,0) = δ(q2,1) =
q1 q2 q1 q2 q1 q2
Contoh 4
δ δ(q0,0) δ(q0,1) δ(q1,0) δ(q1,1) δ(q2,0) δ(q2,1)
= = = = = =
q1 q2 q1 q2 q1 q2
Contoh 4 Inputan 1100 Input
1 1 0 0
Output State
Contoh 4 Inputan 1010 Input
1 0 1 0
Output State
Dari suatu mesin Moore dapat dibuat mesin mealy yang ekuivalen begitu juga sebaliknya. Untuk memperoleh ekuivalensi mesin mealy dari mesin moore, caranya adalah dengan menambahkan label output ke setiap transisi, dan menghapus label output pada setiap state.
Mesin Moore Modulu 3
Mesin Mealy Modulu 3
Mesin Moore Modulus 3
Mesin Mealy Modulus 3
Mesin Mealy Contoh 4
Mesin Moore Contoh 4
Mesin Mealy Contoh 4
Mesin Moore Contoh 4
1. Terdapat suatu mesin moore modulus 4 sebagai berikut, buatlah bentuk formalnya.
2. Buatlah Mesin Mealy yang ekuivalen dari mesin moore nomor 1, dan buatlah bentuk formalnya, dan coba uji dengan 4 jenis output yang menghasilkan 0,1,2,3.
3. Terdapat suatu mealy machine sebagai berikut, buatlah bentuk formalnya.
4. Buatlah Mesin Moore yang ekuivalen dari mesin mealy nomor 3 dan uji dengan 4 jenis output dan sebutkan ini mesin untuk apa.
1. Jawaban Tugas ditulis tangan, dan difoto, kemudian dibuat dalam 1 file PDF 2. Jangan lupa cantumkan nama dan NIM ditugas tersebut 3. Nama file PDF adalah nama mahasiswa_NIM 4. Kumpulkan via elearning masing-masing kelas, untuk kelas B via google classroom 5. Batas waktu pengumpulan sebelum pertemuan berikut (Rabu, 7 April 2021 Pukul 9.00 wita)
