Finite State Automata
Teori bahasa dan automata
merupakan teori yang berkaitan dengan mesin-mesin abstrak yang di dalamnya
terdapat sebuah kajian tentang Finite State Automata yang dapat
diimplementasikan dalam rancangan sebuah Vending Machine. Finite State Automata
dapat dijadikan sebagai logika dasar untuk membuat simulasi Vending Machine.
Finite State Automata atau state
automata berhingga yang biasa disebut FSA, bukanlah mesin fisik tetapi suatu
model matematika dari suatu sistem yang menerima input dan output diskrit (Irawan.,
et al [4]). FSA memiliki state yang banyaknya berhingga, dan dapat
berpindah-pindah dari satu state ke state lain. Perubahan state ini dinyatakan
dengan fungsi transisi. State adalah kondisi atau keadaan atau kedudukan. FSA Tidak
memiliki tempat penyimpanan sehingga kemampuan mengingat terbatas (contoh:
elevator/lift). FSA adalah model matematika yang dapat menerima input dan
mengeluarkan output yang memiliki state yang berhingga banyaknya dan dapat
berpindah dari satu state ke state lainnya berdasarkan input dan fungsi
transisi (Utdirartatmo, [10]).
Finite State Automata didefinisikan sebagai pasangan 5 Tupel
→
M = (Q, ∑, δ, S, F).
Q :
himpunan hingga state
∑ (Sigma) :
himpunan hingga simbol input (alfabet)
δ (Delta) :
fungsi transisi, menggambarkan transisi state FSA akibat pembacaan
simbol input.
Fungsi transisi ini biasanya diberikan dalam bentuk tabel.
S ∈ Q :
state AWAL
F ⊆ Q :
himpunan state AKHIR
 |
Rancangan
diagram transisi aplikasi simulasi Vending Machine yoghurt Walagri
|
Pendefinisian Tuple Mealy machine didefinisikan dengan enam
tupel.
M = (Q,Σ,𝛿,S,Δ, 𝜆)
dengan:
Q :
himpunan state
Σ :
himpunan simbol input
𝛿 :
fungsi transisi
S : state
awal
Δ : himpunan
simbol output
𝜆 :
fungsi output.
Sehingga dapat didefinisikan sebagai berikut:
Q = {q0, q1, q2, q3}
Σ = {a,b,c,d,e,f,M,N,P,k}
S = {q0}
Δ = {A,B,C,D,E,F,o}
Keterangan:
o : tidak
ada
a :
memilih yoghurt rasa leci
b : memilih
yoghurt rasa stroberi
c :
memilih yoghurt rasa original
d : memilih
yoghurt rasa sweet ori
e : memilih
yoghurt rasa vanila
f :
memilih yoghurt rasa coklat
M : uang
sepuluh ribu
N : uang
dua puluh ribu
P : uang
lima puluh ribu
L : dua
lembar uang dua puluh ribu
k : uang
kembalian
Finite State Automata (FSA) dapat
menjadi logika dasar untuk merancang suatu Vending Machine yang fleksibel dalam
proses penjualan yoghurt Walagri dengan berbagai rasa dan variasi kembaliannya.
Konsep FSA pada Vending Machine diterapkan dengan cara FSA membaca setiap
simbol masukan yang diberikan menjadi suatu bahasa yang dikenali oleh FSA.
Mesin selanjutnya akan melakukan proses pengeluaran minuman berdasarkan rasa
yang diinginkan beserta uang kembalian sesuai dengan bahasa yang telah dibaca
oleh FSA. Penerapan konsep FSA dapat menjadi salah satu alternatif untuk
merancang sebuah Vending Machine serta dapat dijadikan bahan pertimbangan dan
acuan untuk pengembangan aplikasi selanjutnya yang sejenis.
 |
16 Kemungkinan Kombinasi State
|
FSA (Finite State Automata) terbagi menjadi dua jenis, dapat
berupa :
1. Deterministic Finite Automata (DFA)
Deterministic Finite Automata (DFA) adalah dari suatu state
ada tepat satu state berikutnya untuk setiap simbol input yang diterima.
2. Nondeterministic Finite Automata (NDFA) / NFA
Nondeterministic Finite Automata (NDFA) / NFA adalah ari
suatu state bisa terdapat 0,1 atau lebih busur keluar (transisi) berlabel
simbol input yang sama.
Deterministic Finite Automata
Deterministic finite automata (DFA) → M = (Q, ∑, δ, S, F),
dimana :
Q :
himpunan state/kedudukan
∑ :
himpunan simbol input
∂ : fungsi
transisi,
Dimana, ∂ ∈ Q x ∑ → Q
S : State
awal (initial state)
F :
himpunan state akhir (Final State)
Language → L(M) : (x | ∂(S,x) di dalam F)
Pada DFA dari suatu state ada tepat satu state berikutnya
untuk setiap simbol input
(masukan) yang di terima.
Konfigurasi DFA contoh 1 secara formal adalah sebagai
berikut :
Q = {q0, q1, q2}
Σ = {a, b}
S = q0
F = {q2}
Fungsi-fungsi transisinya sebagai berikut :
δ (q0, a) = q0, δ (q0, b) = q1,
δ (q1, a) = q1, δ (q1, b) = q2,
δ (q2, a) = q1, δ (q2, b) = q2.
Jika disajikan dalam tabel transisi :
δ
|
a
|
b
|
q0
|
q0
|
q1
|
q1
|
q1
|
q2
|
q2
|
q1
|
q2
|
* Dalam DFA, selalu dan pasti terdapat satu state berikutnya
untuk setiap pasangan state
input.
Penelusuran/Tracking
Telusurilah, apakah kalimat-kalimat berikut diterima DFA di
atas:
abababaa, aaaabab , aaabbaba
Jawab :
δ (q0,abababaa) ⇒ δ
(q0,bababaa) ⇒ δ (q1,ababaa) ⇒
δ (q0,babaa) ⇒ δ
(q1,abaa) ⇒ δ (q0,baa) ⇒ δ (q1,aa) ⇒
δ (q0,a) ⇒ q0
Tracking berakhir di q0 (state AKHIR) ⇒
kalimat abababaa diterima
Kesimpulan :
Sebuah kalimat diterima oleh DFA di atas jika tracingnya
berakhir di salah satu state AKHIR.
Non Deterministic Finite Automata (NFA)
Non Deterministic finite automata (NFA) → M
= (Q, ∑, δ, S, F)
dimana :
Q :
himpunan state/kedudukan
∑ :
himpunan simbol input
∂ : fungsi
transisi
Dimana, ∂ ∈ Q x (∑ ⋃
ε) → P(Q)
P(Q) : set of all
subsets of Q
S : State
awal (initial state)
F :
himpunan state akhir (Final State)
Language → L(M) : (x | ∂(S,x) di dalam F)
Sebuah kalimat di terima NFA jika:
Salah satu tracking-nya berakhir di state AKHIR, atau himpunan
state setelah membaca string tersebut mengandung state AKHIR.
Telusurilah, apakah kalimat-kalimat berikut diterima NFA di
atas :
ab, abc, aabc, aabb
Jawab:
δ(q0 ,ab) ⇒ δ(q0,b)
∪
δ(q1 ,b) ⇒ {q0, q2} ∪ {q1 } = {q0
, q1 , q2}
Himpunan state TIDAK mengandung state AKHIR ⇒
kalimat ab tidak
diterima
δ(q0 ,abc) ⇒ δ(q0
,bc) ∪
δ(q1 ,bc) ⇒ { δ(q0
,c) ∪
δ(q2 ,c)}∪δ(q1
, c)
{{ q0 , q3 }∪{ q2 }}∪{ q1 } = {q0
, q1 , q2 ,q3 }
Himpunan state TIDAK mengandung state AKHIR ⇒
kalimat abc tidak Diterima.
State
|
a
|
b
|
S0
|
S1
|
S2
|
S1
|
S1
|
S1
|
S2*
|
S2
|
-
|
State
|
a
|
b
|
S0
|
S1
|
{S0, S2}
|
S1
|
S1
|
S1
|
S2*
|
S2
|
-
|
Berdasarkan contoh Deterministic Finite Automata
(DFA) dan Non Deterministic Finite Automata (NFA) yang ada di atas, terlihat
perbedaan antara DFA dan NFA yaitu :
Pada Deterministic Finite Automata, jika suatu
state diberi inputan maka state tersebut akan selalu tepat menuju satu state. Pada
Non Deterministic Finite Automata, jika suatu state diberi inputan maka mungkin
saja bisa menuju ke beberapa state berikutnya. Dapat dilihat di S0, jika diberi
inputan b bisa menuju ke S1 dan S2.
Ekuivalensi Antar Deterministic Finite Automata
Untuk suatu bahasa regular, kemungkinan ada sejumlah Deterministic
Finite Automata yang dapat menerimanya. Perbedaannya hanyalah jumlah state
yang dimiliki otomata-otomata yang saling ekuivalen tersebut. Tentu saja, dengan alasan
kepraktisan, kita memilih otomata dengan jumlah state yang lebih sedikit.
Sasaran kita di sini adalah
mengurangi jumlah state dari suatu Finite State Automata, dengan tidak mengurangi kemampuannya semula untuk menerima suatu bahasa.
Ada dua buah istilah baru yang perlu kita ketahui yaitu :
1. Distinguishable yang berarti dapat dibedakan.
2. Indistinguishable yang berarti tidak dapat dibedakan.
Dua DFA M1 dan M2 dinyatakan ekivalen apabila L(M1)
= L(M2)
Reduksi Jumlah State Pada FSA
• Reduksi dilakukan untuk mengurangi jumlah state
tanpa mengurangi
kemampuan untuk menerima suatu bahasa seperti
semula (efisiensi)
• State pada FSA dapat direduksi apabila terdapat
useless state
• Hasil dari FSA yang direduksi merupakan
ekivalensi dari FSA semula
Contoh Reduksi Jumlah State
Langkah Penyelesaian Soal
diatas:
Langkah Pertama
Identifikasilah setiap kombinasi
state yang mungkin :
Kombinasi state yang mungkin
adalah :
(q0 , q1 )
(q0 , q2 )
(q0 , q3 )
(q0 , q4 )
(q1 , q2 )
(q1 , q3 )
(q1 , q4 )
(q2 , q3 )
(q2 , q4 )
(q3 , q4 )
Langkah Kedua
State yang berpasangan dengan
state akhir (q4) merupakan state yang distinguishable
(q0 , q1 )
(q0 , q2 )
(q0 , q3 )
(q0 , q4 ) :
Distinguishable
(q1 , q2 )
(q1 , q3 )
(q1 , q4 ) : Distinguishable
(q2 , q3 )
(q2 , q4 ) : Distinguishable
(q3 , q4 ) : Distinguishable
Langkah Ketiga
Untuk pasangan state yang lain
jika masing-masing state mendapat input yang sama, maka bila satu state
mencapai state akhir dan yang lain tidak mencapai state akhir maka dikatakan
distinguishable. Untuk (q0 , q1 ) :
δ (q0 , 1) = q3
δ (q1 , 1) = q4
δ (q0 , 0) = q1
δ (q1 , 0) = q2
Maka (q0 , q1) :
Distinguishable
Untuk (q0 , q2 ) :
δ (q0 , 1) = q3
δ (q2 , 1) = q4
δ (q0 , 0) = q1
δ (q2 , 0) = q1
Maka (q0 , q2) :
Distinguishable
Untuk (q0 , q3 ) :
δ (q0 , 1) = q3
δ (q3 , 1) = q4
δ (q0 , 0) = q1
δ (q3 , 0) = q2
Maka (q0 , q3) : Distinguishable
Untuk (q1 , q 2 )
δ (q1 , 1) = q4
δ (q2 , 1) = q4
δ (q1 , 0) = q2
δ (q2 , 0) = q1
Maka (q1 , q2 ) :
Indistinguishable
Untuk (q1 , q3 )
δ (q1 , 1) = q4
δ (q3 , 1) = q4
δ (q1 , 0) = q2
δ (q3 , 0) = q2
Maka (q1 , q3 ) :
Indistinguishable
Untuk (q2 , q3 )
δ (q2 , 1) = q4
δ (q3 , 1) = q4
δ (q2 , 0) = q1
δ (q3 , 0) = q2
Maka (q2 , q3 ) :
Indistinguishable
Langkah Keempat
Maka Didapatkan pasangan state
sebagai berikut :
(q0 , q1 ) : Distinguishable
(q0 , q2 ) : Distinguishable
(q0 , q3 ) : Distinguishable
(q0 , q4 ) : Distinguishable
(q1 , q2 ) : Indistinguishable
(q1 , q3 ) : Indistinguishable
(q1 , q4 ) : Distinguishable
(q2 , q3 ) : Indistinguishable
(q2 , q4 ) : Distinguishable
(q3 , q4 ) : Distinguishable
Langkah Kelima
Kelompokkan pasangan state yang
indistinguishable :
(q1 , q2 ) : Indistinguishable
(q1 , q3 ) : Indistinguishable
(q2 , q3 ) : Indistinguishable
Langkah Keenam
Karena q1 indistinguishable
dengan q2 dan q2 indistinguishable dengan q3, maka bisa dikatakan bahwa q1, q2,
dan q3 saling indistinguishable dan dapat dijadikan satu state.
Langkah Terakhir sekaligus Hasil Penyederhanaan
Sehingga hasil penyederhanaannya
adalah sebagai berikut :
Daftar Pustaka
No comments:
Post a Comment