FINITE STATE AUTOMATA DENGAN OUTPUT

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, Δ, λ), 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 3. Dimana input dinyatakan dalam biner. Mesin Moore yang bersesuaian bisa dilihat pada gambar 1. Konfigurasi mesin sebagai berikut:
Q = {q₀,q₁,q₂}
Σ = {0,1} (input dalam biner)
δ = {0,1,2} (untuk output-nya pada kasus mod dengan 3 maka sisanya kemungkinan
adalah (0,1,2)
S = q₀
λ (q₀) = 0
λ (q₁) =1
λ (q₂) =2

Misalkan saja
5 mod 3 = ?
input 5 dalam biner 101
bila kita masukkan 101 ke dalam mesin, urutan state yang dicapai: q₀,q₁,q₂,q₂
Perhatikan state terakhir yang dicapai adalah q₂, λ (q₂) =2, maka 5 mod 3 = 2

10 mod 3 =?
input 10 dalam biner 1010
bila kita masukkan 1010 ke dalam mesin, urutan state yang dicapai: q₀,q₁,q₂,q₂, q₁
λ (q₁) =1, maka 10 mod 3 = 1

Mesin Mealy

Bila output pada mesin Moore berasosiasi dengan state, maka output pada Mesin Mealy akan berasosiasi dengan transisi. Mesin Mealy sendiri didefinisikan dalam 6 tupel, M = (Q, Σ, δ, S, Δ, λ), dimana:
Q = himpunan state
Σ = himpunan symbol input
δ = fungsi transisi
S = state awal, S ε Q
Δ = himpunan output
λ = fungsi output untuk setiap transisi

Contoh penerapan Mesin Mealy kita lihat pada gambar 2.
Mesin itu akan mengeluarkan output apakah menerima (Y) atau menolak (T), suatu masukan. Dimana mesin akan mengeluarkan output ‘Y’ bila menerima untai yang memiliki akhiran 2 simbol berturutan yang sama, atau secara formal dalam ekspresi regular:

(0+1)*(00+11)

Contoh input yang diterima :
01011, 01100, 1010100, 10110100, 00, 11, 100, 011, 000, 111
Konfigurasi dari Mesin Mealy tersebut:
Q = {q₀,q₁,q₂}
Σ = {0,1}
Δ = {Y,T}
S = q0
λ (q₀,0) = T
λ (q₀,1) = T
λ (q₁,0) = Y
λ (q₁,1) = T
λ (q₂,0) = T
λ (q₂,1) =Y