Institute Teknologi PLN Jakarta
Dosen : Dine Tiara Kusuma S.T., M.Kom
EKUIVALENSI ANTAR DETERMINISTIC FINITE AUTOMATA
Sasaran kita disini adalah mengurangi jumlah state dari
suatu Finite State Automata, dengan tidak mengurangi kemampuannya semula untuk
menerima suatu bahasa. Ada dua istilah baru yang perlu kita ketahui yaitu :
1. Distinguishable, artinya berarti dapat dibedakan.
2. Indistinguishable, artinya berarti tidak dapat dibedakan.
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 ekuivalensi dari FSA semula.
Pasangan State dapat dikelompokkan berdasarkan :
1. Distinguishable State (dapat dibedakan)
- Dua state p dan q dari suatu DFA dikatakan indistinguishable apabila :
- δ(q,w) ∈ F dan δ(p,w) ∈ F atau δ(q,w) ∉ F dan δ(p,w) ∉ F \
- Untuk semua w ∈ S*
2. Indistinguishable State (tidak dapat dibedakan)
- Dua state p dan q dari suatu DFA dikatakan distinguishable jika ada string w ∈ S* hingga :
- δ(q,w) ∈ F dan δ(p,w) ∉ F
Reduksi Jumlah State Pada FSA – Relasi
Pasangan dua buah state memiliki salah satu kemungkinan : distinguishable atau indistinguishable, tetapi tidak kedua-duanya. Dalam hal ini terdapat sebuah relasi.
Jika p dan q indistinguishable, dan q dan r indistinguishable maka p, r indistinguishable dan p,q,r indistinguishable.
Dalam melakukan evaluasi state, didefinisikan suatu relasi : Untuk Q yang merupakan himpunan semua state.
- D adalah himpunan state-state distinguishable, dimana D ⊂ Q
- N adalah himpunan state-state indistinguishable, dimana N ⊂ Q·
- maka, x ∈ N jika x ∈ Q dan x ∉ D
Contoh :
Lakukan Reduksi
state pada DFA dibawah ini?
- State q5 tidak dapat dicapai dari state awal dengan jalan apapun (useless state). Hapus state q5.
- Catat state-state distinguishable, yaitu : q4 ∈ Fsedang q0, q1, q2, q3 ∉ sehingga pasangan-pasangan state :
(q0, q1)
(q0, q2)(q0, q3)(q0,q4)(q1,q2)(q1,q3)(q1,q4)(q2,q3)(q2,q4)(q3,q4)
3. Reduksi jumlah state pada FSA – Step.
(q0, q1)
(q0, q2)
(q0, q3)
(q0, q4) => Distuingishable
(q1, q2)
(q1,
q3)
(q1,
q4) => Distuingishable
(q2,
q3)
(q2,
q4) => Distuingishable
(q3, q4) => Distuingishable
4. Cari status pasangan lainnya, dengan memperhatikan inputan yang tersedia yaitu 0 dan 1 :
Pasangan
(q0, q1)
·
δ(q0,
0) = q1 dan δ(q1, 0) = q2, => (q1, q2) belum terdefinisi
·
δ(q0,
1) = q3 dan δ(q1, 1) = q4, => (q3, q4) Distinguishable
·
Maka
(q0, q1) adalah Distinguishable
