Blog Teori Bahasa Dan Otomata tentang Ekuivalensi Antar Deterministic Finite Automata || Siti Nurul Maghfirah L_ 202131125

                                                                   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?

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.

               (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

v