Mesin Moore & FSA

Mesin Moore

Mesin Moore itu finite state machine yang outputnya berasosiasi dengan state, atau tertulis pada setiap state sehingga jumlah state sama dengan jumlah output. Selain itu mesin moore tidak memiliki final state.

Secara Mesin Moore memiliki 6 tuple dimana M= { Q, ∑, δ, S, Δ, λ }

Q    =   Himpunan State

∑    =   Himpunan Syimbol Input

δ     =   Fungsi Transisi

S     =   Simbol State Awal

Δ    =   Himpunan Output

λ     =   Fungsi Output untuk Setiap State

Contoh Mesin Moore Mod 7

Penjelasan : 

Q = { q0, q1, q2, q3, q4, q5, q6 }

∑ = { 0,1 }

S = { q0 }

Δ = { 0, 1, 2, 3, 4, 5, 6 }

λ = { (q0)= 0; (q1)= 1; (q2)= 2; (q3)= 3; (q4)= 4; (q5)= 5; (q6)= 6; }

δ  =  

δ	0	1
q0	q0	q1
q1	q2	q3
q2	q6	q4
q3	q5	q0
q4	q3	q4
q5	q5	q6
q6	q1	q2

Uji Input :

8 mod 7 ?

• Input 8 dalam biner  = 1000
• Urutan state yang dicapai = q0, q1, q2, q6, q1
• State terakhir yang dicapai = q1,  λ (q1) = 1
• Maka 8 mod 7 = 1 

9 mod 7 ?

• Input 9 dalam biner  = 1001
• Urutan state yang dicapai = q0, q1, q2, q6, q2
• State terakhir yang dicapai = q2,  λ (q2) = 2
• Maka 9 mod 7 = 2

10 mod 7 ?

• Input 10 dalam biner  = 1010
• Urutan state yang dicapai = q0, q1, q2, q4, q3
• State terakhir yang dicapai = q3,  λ (q3) = 3
• Maka 10 mod 7 = 3

11 mod 7 ?

• Input 11 dalam biner  = 1011
• Urutan state yang dicapai = q0, q1, q2, q4, q4
• State terakhir yang dicapai = q4,  λ (q4) = 4
• Maka 11 mod 7 = 4

12 mod 7 ?

• Input 12 dalam biner  = 1100
• Urutan state yang dicapai = q0, q1, q3, q5, q5
• State terakhir yang dicapai = q5,  λ (q5) = 5
• Maka 12 mod 7 = 5

=======================================================================

FSA

Finite State Automata (FSA) adalah model matematika yang dapat menerima input dan mengeluarkan output yang memiliki state, berhingga banyaknya dan dapat perpindah dari satu state ke state lainnya berdasarkan input dan fungsi transisi.

Secara formal finite state automata memiliki 5 tuple diman M = { Q, Σ, S, F, δ }

Q : Himpunan State / Kedudukan

Σ : Himpunan Simbol Input 

δ : Fungsi Transisi

S : State Awal / kedudukan Awal

F : Himpunan State Akhir 

Contoh Mesin Abstrak FSA 

Penjelasan :

Q : { q0, q1, q2, q3, q4, q5 }

Σ :{0, 1}

S :{q0}

F : {q4}

δ :  

δ	0	1
q0	q3	q2
q1	q4	q5
q2	-	q3
q3	-	q1
q4	q5	q2
q5	q2	q4

Uji Input :

1110 = Diterima

0011 = Ditolak

0110 = Ditolak

0111 = Diterima

===============================================================

Berikut Lembar Jawaban Saya :