TEORI BAHASA DAN OTOMATA

TEORI BAHASA DAN OTOMATA

FSA dengan Output 

1. Suatu keterbatasan dari finite state automata yang sudah dipelajari selama ini keputusannya terbatas pada diterima atau ditolak.
2. Otomata tersebut biasa disebut sebagai accepter, dalam hal ini finite state accepter.
3. Kita bisa mengkonstruksi sebuah finite state automata yang memiliki keputusan beberapa keluaran/output, dalam hal ini otomata tersebut akan dikenal sebagai transducer.
4. FSA dengan output antara lain adalah mesin Moore dan mesin Mealy.

Mesin More
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.

Contoh Penerapan Mesin Moore
Misal 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: 1. Q = {q0,q1,q2}
2. ∑ = {0,1} (input dalam biner)
3. Δ = {0,1,2} (untuk output-nya pada kasus mod dengan 3 maka sisanya kemungkinan adalah 0,1,2)
4. S = q0
5. λ (q0) = 0 ; λ (q1) =1 ;λ (q2) =2

5 mod 3 = ?

• Input 5 dalam biner : 101 
• Urutan state yang dicapai: q0,q1,q2 
• Perhatikan state terakhir yang dicapai adalah q2, λ(q2)=2, maka 5 mod 3 = 2

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
Mesin ini 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)

Ekivalensi Mesin Moore dan Mesin Mealy
Dari suatu Mesin Moore dapat dibuat Mesin Mealy yang ekivalen, begitu juga sebaliknya.
Untuk mesin Mealy pada gambar 2 dapat dibuat Mesin Moore yang ekivalen yaitu gambar 3.
Bisa dilihat state pada mesin Moore dibentuk dari kombinasi state pada Mealy dan banyaknya output.
Karena jumlah state Mealy = 3, dan jumlah output = 2, maka jumlah state pada Moore yang ekivalen = 6.

Bisa dilihat konfigurasi Mesin Moore yang dibentuk:

1. Q = {q0Y,q0T,q1Y,q1T,q2Y,q2T} 
2. ∑ = {0,1} 
3. Δ = {Y,T} 
4. S = q0 
5. λ (q0Y) = Y ; λ (q0T) = T ;

λ (q1Y) = Y ; λ (q1T) = T ;

λ (q2Y) = Y ; λ (q2T) = T ;

Bila diperhatikan dari gambar di samping, state q0Y dapat dihapus karena tidak ada busur yang mengarah ke state tersebut.

Untuk memperoleh ekivalensi mesin Mealy dari suatu mesin Moore caranya lebih mudah, cukup dengan menambahkan label output ke setiap transisi dan menghapus label output pada setiap state.
Dapat dilihat gambar 4 merupakan mesin Mealy yang ekivalen dengan mesin Moore pada gambar 1.