Teori Bahasa Dan Automata ( Mesin Moore )

Mesin Moore

     Suatu keterbatasan dari Finite State Automata yang sudah dipelajari adalah keputusannya terbatas pada diterima atau ditolak saja. Automata tersebut disebut sebagai accepter, dalam hal ini disebut Fiite State Accepter.

Kita dapat mengkonstruksi suatu Finite State Automata yang memiliki keputusan beberapa keluaran atau output, dalam hal ini disebut Finite State Transducer. Pada mesin Moore, output akan berasosiasi dengan state.

 Mesin Moore memiliki 6 (Enam) tupel, M = (Q, Σ, δ, S, Δ, λ).

 Dimana :

Q = Himpunan State

Σ = Himpunan Simbol Input

δ = Fungsi Transisi

S = State Awal

Δ = Himpunan Output

λ = Fungsi Output untuk setiap State

Keterangan : Komponen state akhir dari Deterministic Finite Automata dihilangkan, karena disini keputusan dimunculkan sebagai output.

Contoh 1 : 

 

Penerapan Mesin Moore Kita akan mencari nilai sisa pembagian (modulus) suatu bilangan dengan 5. Dimana input dinyatakan dalam biner.

 Konfigurasi : Q = {q0, q1, q2,q3,q4}

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

 S = q0

 Δ = {0, 1, 2, 3, 4} (untuk outputnya pada kasus mod dengan 5 maka sisanya kemungkinan adalah 0, 1, 2, 3, 4)

λ(q0) = 0

λ(q1) = 1

λ(q2) = 2 

λ(q3) =3

λ(q4) = 4 

Gambar Mesin Moore untuk modulus 5 : 

                        run dengan step                                                  run dengan fast run

Pembuktian : 

•6 mod 5 = ? input 6 dalam biner 011 bila kita masukkan 011 kedalam mesin, urutan state yang dicapai adalah : q0, q0, q3, q1 State terakhir yang dicapai adalah q1, λ(q1) = 1 Maka 6 mod 5 = 1

 

                         run dengan step                                         run dengan fast run

 Pembuktian :

•14 mod 3 = ? input 14 dalam biner 0111 bila kita masukkan 0111 kedalam mesin, urutan state yang dicapai adalah : q0, q0, q3, q1, q4 State terakhir yang dicapai adalah q4, λ(q4) = 4 Maka 14 mod 5 =4

                         run dengan step                                    run dengan fast run

 Pembuktian :

 •27 mod 5 = ? input 27 dalam biner 01110 bila kita masukkan 01110 kedalam mesin, urutan state yang dicapai adalah : q0, q0, q3, q1, q4, q2 State terakhir yang dicapai adalah q2, λ(q2) = 2 Maka 27 mod 5 = 2

Sekian materi yang saya laporkan. jika ada tambahan atau kritik dan saran dapat menulis kan di dalam kolom komentar !!!