GRAMMAR OTOMATA & FINITE STATE AUTOMATA
Grammar otomata adalah bentuk abstrak yang dapat diterima untuk membangkitkan suatu kalimat otomata berdasarkan suatu aturan tertentu. Grammar otomata didefinisikan sebagai pasangan 4 tupel yaitu (V,T,S,P) atau dituliskan sebagai berikut :
G = {V,T,S,P}
ket :
V = Himpunan simbol variabel
T = Himpunan simbol terminal
S = Simbol awal
P = Kumpulan aturan produksi
Langkah pertama yang akan kita lakukan untuk membuat sebuah mesin abstrak grammar otomata adalah membuat aturan produksi (production) terlebih dahulu. Berikut adalah aturan produksi (production) yang saya buat.
Jika mesin abstrak sudah terbentuk selanjutnya kita akan tentukan 4 pasangan tupel grammar yang sudah dijelaskan diatas.
G = {V,T,S,P}
--------------
V = {D,I,A,N,P}
T = {x,y,z}
S = q0
P = {D → zI, D → xD, I → N, N →𝞴 , I → xA, P → yD, A → zN, N → yA}
Jadi dapat di simpulkan,
G = ( {D,I,A,N,P} , {x,y,z}, q0 , {D → zI, D → xD, I → N, N →𝞴 , I → xA, P → yD, A → zN, N → yA})
---------------------------
Finite State Automata adalah mesin abstrak berupa sistem model matematika yang dapat menerima input dan mengeluarkan output yang memiliki state berhingga banyaknya, dan dapat berpindah dari satu state ke state lainnya berdasarkan input dan fungsi transisi. Mekanisme FSA tidak memiliki tempat penyimpanan/memory dan hanya bisa mengingat state terkini.
Finite State Automata memiliki bentuk formal dengan 5 buah tupel, yaitu :
M = (Q, Σ, 𝛅, A, F)
Ket :
1. Q = Himpunan State
2. Σ = Himpunan Simbol Input
3. 𝛅 = Fungsi Transisi
4. A = State Awal
5. F = Final State
Diatas kita sudah mendapatkan mesin abstrak dari productin grammar yang kita convert ke dalam FSA, selanjutnya kita akan menentukan bentuk formal dari 5 pasangan tupel.
M = (Q, Σ, 𝛅, A, F)
----------
M = { q0 q1 q2 q3 q4 q5 }
Σ = { x,y,z}
𝛅 = Fungsi Transisi
A = q0
F ={ q5 }
-------
Jadi dapat di simpulkan, M = ( { q0 q1 q2 q3 q4 q5 }, { x,y,z}, 𝛅, q0 , { q5 })
Uji Input String dari FSA diatas :
Lembar jawaban :
Komentar
Posting Komentar