UAS Teori Bahasa dan Otomata
Contoh Mesin Grammar dan Mesin Mealy yang akan saya buat.
Grammar adalah Sebuah bentuk mesin abstrak yang dapat diterima ( Accept ) untuk membangkitkan suatu kalimat otomata berdasarkan aturan tertentu .
Grammar dinyatakan oleh 4 Tupple Yaitu :
G = (V,TS,P).
V = Himpunan Variabel (Huruf Besar)
T = Himpunan Terminal (Huruf Kecil)
S = State Awal
P = Himpunan Produksi
Langkah awal untuk membuat mesin Grammar adalah sebagai berikut:
1. Buka aplikasi Jflap lalu pilih Grammar
4. Setelah itu klik tombol show all dan hasil mesin abstraknya seperti ini
Berikut hasil tupplenya:
V = (S,A,B,C,D)
T = (a,b,c,d)
S = (q2)
P = S-aB, C-cA, B-aC, D-bC, A-aC, B-dA, D-cB, S-aD, C-λ
Langkah selanjutnya mesin abstrak grammar dikonversikan ke definisi
Finite State Automata adalah Mesin abstrak berupa sistem model matematika dengan masukan dan keluaran diskrit yang dapat mengenali bahsa paling sederhana dan dapat diimplementasikan secara nyata.
Finite State Automata dinyatakan oleh pasangan 5 Tupple yaitu:
M=(Q , Σ , δ , S , F )
Q = himpunan stateΣ = himpunan simbol inputδ = fungsi transisi δ : Q × ΣS = state awal / initial state , S ∈ QF = state akhir, F ⊆ Q
Berikut ini contoh dari mesin abstrak FSA dan hasil tupple nya
Uji Input
B. Mesin Mealy
Mesin Mealy adalah finite-state machine
yang nilai outputnya ditentukan oleh state dan inputnya.
Mesin Mealy adalah deterministic
finite-state transducer, untuk setiap keadaan dan masukan, paling banyak satu
transisi dimungkinkan. Diagram mesin mealy menghubungkan nilai output dengan
masing-masing transisi.
Contoh Mesin Mealy
S = Himpunan State
S0 = State awal
∑ = Himpunan input
∆ = Himpunan output
T = Fungsi Transisi
G = Fungsi output
Fungsi Transisi:
G= {q0,q1,q2,q3,q4,q5}
∑= 0,1
∆= {Y,T}
S= q0
λ= (q0,0)=T
λ= (q0,1)=T
λ= (q1,0)=Y
λ= (q1,1)=Y
λ= (q2,0)=T
λ= (q2,1)= -
λ= (q3,0)=T
λ= (q3,1)=Y
λ= (q4,0)=Y
λ= (q4,1)= -
λ= (q5,0)=Y
λ= (q5,1)=T
Sekian dan Terimakasih
