Institut 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?
1. State q5 tidak dapat dicapai dari state
awal dengan jalan apapun (useless state).
Hapus state q5.
2. 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
Pasangan state :
(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
