Selamat datang di Blog Saya, kali ini saya akan menjelaskan tentang Mesin Abstrak Grammar dan FSA pada Auotomata.
Langsung saja kita mulai ya.
A. Grammar
Grammar adalah bentuk abstrak yang dapat diterima (accept) untuk membangkitkan suatu kalimat otomata berdasarkan suatu aturan tertentu.
Tata Bahasa (grammar) didefinisikan dengan empat (4) tupel G = ({V, T, P, S}) dimana :
V = Himpunan simbol variabel / non terminal
T = Himpunan simbol terminal
P = Kumpulan aturan produksi
S = Simbol awal
Contoh :
Keterangan :
q2 = (S) melewati jalur a menuju q4 = (E) menjadi S -> aE
Secara formal dapat ditulis :
V = {S,E,A,B,C}
T = {a,b}
P = {S ->aE, E->bB, E->aA, A->C, B->a, C->b}
S = S (Simbol Awal)
B. FSA
Secara formal FSA dinyatakan dengan 5-tuple atau M =(Q, Σ, δ, q0, F):
a. Q = himpunan state/kedudukan
b. Σ = abjad, himpunan simbol input
c. δ = transition function
d. q0 ∈ Q = start state
e. F ⊆ Q = set of accept (or final) states
Jenis - jenis Otomata
1. DFA (Deterministic Finite Automata)
2. NFA (Nondeterministic Finite Automata)
3. Pushdown Otomata
Contoh NFA :
Keterangan :
Q = {q0, q1, q2,q3,q4, q5}
Σ = {0, 1}
δ = is described as
0
|
1
|
|
q0
|
q1
|
q0
|
q1
|
q2, q5
|
|
q2
|
q3, q5
|
|
q3
|
q5
|
|
q4
|
q5
|
|
q5
|
q4
|
q0 = is the start state, and
F = {q5}
Hasil Uji Input :
Demikian sedikit yang dapat saya sampaikan mengenai mesin abstrak Grammar dan FSA , apabila ada kesalahan dalam penulisan, saya mohon maaf yang sebesar-besarnya. Semoga apa yang saya posting dapat bermanfaat bagi kita semua.
Terimakasih :-)
