UAS - Mesin Moore Modulus 4

Mesin moore adalah otomasi fasa berhingga (finite stateautomaton) di mana keluarannya ditentukan hanya oleh fasa saat itu(dan tidak terpengaruh oleh bagian masukan/input). Diagram fasa (statediagram) dari mesin Moore memiliki sinyal keluaran untuk masing-masing fasa.

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

Contoh kasus :

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

Konfigurasi :
Q = {q0, q1, q2, q3}
Σ = {0, 1}
S = q0
Δ = {0, 1, 2, 3}
λ = Q -> Δ , yaitu λ (q0) = j untuk j = 0,1,2,3
λ (q0) = 0
λ(q1) = 1
λ(q2) = 2
λ(q3) = 3
δ = Q x Σ -> Q didefinisikan sebagai berikut:

Gambar Mesin Moore modulus 4 :

Pembuktian:

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

• 4 mod 4 = ?
  input 4 dalam biner 0100
  bila kita masukkan 0100 kedalam mesin, urutan state yang dicapai adalah : q0, q0 , q1, q2, q1 
  State terakhir yang dicapai adalah q1, λ(q1) = 1 
  Maka 4 mod 4 = 0

• 9 mod 4 = ?
  input 9 dalam biner 1001
  bila kita masukkan 1001 kedalam mesin, urutan state yang dicapai adalah : q0, q1 , q2, q1, q0 
  State terakhir yang dicapai adalah q0, λ(q0) = 0 
  Maka 9 mod 4 = 0

Sekian.

UTS - FSA and Grammar

1. Finite State Automata (FSA)

Finite State Automata (FSA) adalah mesin abstrak berupa sistem model matematika dengan masukan dan keluaran diskrit yang dapat mengenali bahasa paling sederhana (bahasa reguler) dan dapat diimplementasikan secara nyata.

Pada FSA mesin mula-mula dalam state S0 dan menerima sederatan masukan yang dapat mengubahnya ke state-state berikutnya. Dalam FSA juga dikenal himpunan state-state tertentu yang disebut sabagai FINAL STATE. Perubahan dari satu state ke state berikutnya mengikuti sturan tertentu yang dirumuskan sebagai suatu FUNGSI transisi

Secara formal FSA dapat didefinisikan sebagai TUPLE-5 : (Q, ∑, δ, S, F). 
Q : himpunan hingga state 
∑ : himpunan hingga simbol input (alfabet) 
δ : fungsi transisi, menggambarkan transisi state FSA akibat pembacaan simbol input. Fungsi transisi ini biasanya diberikan dalam bentuk tabel. 
S : state awal
F : himpunan state akhir

Contoh :

2. Regular Grammer

Grammar adalah bentuk abstrak yang dapat diterima (accept) untuk membangkitkan suatu kalimat otomata berdasarkan suatu aturan tertentu.

Grammar G didefinisikan sebagai pasangan 4 tuple : V , T , P, dan S, dan dituliskan sebagai G(V , T , P, S), dimana :
V       : himpunan  simbol-simbol variable / non terminal
T       : himpunan simbol-simbol terminal
P       : himpunan produksi 
S    : simbol awal (atau simbol start)

Contoh Kasus Grammer