Rizky Darmawan

Rabu, 08 Januari 2020

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 :

Kamis, 31 Oktober 2019

Grammar Otomata & Finite State Otomata

A. Grammar

Konsep Dasar Grammar

Teori Otomata itu teori mengenai mesin-mesin abstrak, dan berkaitan erat dengan teori bahasa formal. ada beberapa hal yang berkaitan dengan Otomata, yaitu Grammar. Grammar adalah bentuk abstrak yang dapat diterima (accept) untuk membangkitkan suatu kalimat otomata berdasarkan suatu aturan tertentu.

Grammar Memiliki 4 tuple : G : (V, T, P, S)

V : Himpunan Simbol Variabel
T : Himpunan Terminal
P : Kumpulan aturan produksi
S : State awal

Contoh Soal Grammar

Aturan Produksi

Hasil convert to FA

Penjelasan dengan 4 tuple grammar :

V : A, B, C, D

T : y, u, k, m, a, e, n, x

P          : A => yB
            B => uB
            B => k
            C => m
            A => e
            B => aC
            C => xD
            D => n

S : q0

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

B. Finite State Otomata

Konsep dasar FSA

Secara formal finite state automata memiliki 5 tuple :