Ekuivalensi Antar Deterministic Finite Automata

 Ekuivalensi Antar Deterministic Finite Autamata

    Ekuivalensi Antar Deterministic Finite Automata 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 : 

• Distinguishable yang berarti dapat dibedakan. 

• Indistinguishable yang berarti tidak dapat dibedakan.

Contoh Ekuivalensi antar DFA:

    Berdasarkan gambar diatas dapat diambil kesimpulan bahwa walaupun kedua gambar DFA diatas bebeda tetapi hasil output yang diterimanya tetap sama yaitu hanya dapat menerima inputan yang mengandung a. 

    

    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.

Pasangan State dapat dikelompokkan berdasarkan :

1. Indistinguishable 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. Distinguishable State (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

Langkah Reduksi State pada FSA

Contoh Soal:

Langkah :

1. State q5 tidak dapat dicapai dari state awal dengan jalan apapun (useless state). Hapus state q5 

Catat state-state distinguishable, yaitu : 

q4 ∈ F sedang q0, q1, q2, q3 ∉F sehingga pasangan 

Pasangan State : 

(q0,q1) 

(q0,q2) 

(q0,q3) 

(q0,q4) 

(q1,q2) 

(q1,q3) 

(q1,q4) 

(q2,q3) 

(q2,q4) 

(q3,q4)

2. Pasangan State : 

(q0,q1) 

(q0,q2) 

(q0,q3) → Distinguisable

(q0,q4) → Distinguisable 

(q1,q2) 

(q1,q3) → Distinguisable

(q1,q4) → Distinguisable 

(q2,q3) → Distinguisable

(q2,q4) → Distinguisable 

(q3,q4) → Indistinguisable

3. 

■ Pasangan (q0,q1) 

- δ(q0, 0) = q1 dan δ(q1, 0) = q2 ➔ (q1 , q2) = belum terdefinisi  

- δ(q0, 1) = q2 dan δ(q1, 1) = q3 ➔ (q2 , q3) = Distinguishable

Maka (q0, q1) adalah Distinguishable

■ Pasangan (q0,q2) 

- δ(q0, 0) = q1 dan δ(q2, 0) = q2 ➔ (q1 , q2) = belum terdefinisi  

- δ(q0, 1) = q2 dan δ(q2, 1) = q4 ➔ (q2 , q4) = Distinguishable

Maka (q0, q1) adalah Distinguishable

■ Pasangan (q1,q2) 

- δ(q1, 0) = q2 dan δ(q2, 0) = q2 ➔ (q1 , q2) = belum terdefinisi  

- δ(q1, 1) = q3 dan δ(q2, 1) = q4 ➔ (q3 , q4) = Indistinguishable

Maka (q1, q2) adalah Indistinguishable

■ Pasangan (q3,q4) 

- δ(q3, 0) = q3 dan δ(q4, 0) = q4 ➔ (q3 , q4) = Indistinguishable  

- δ(q3, 1) = q3 dan δ(q4, 1) = q4 ➔ (q3 , q4) = Indistinguishable 

Maka (q3, q4) adalah Indistinguishable 

4. Menentukan indistingushable

Pasangan State : 

(q0,q1) → Distinguishable 

(q0,q2) → Distinguishable 

(q0,q3) → Distinguishable 

(q0,q4) → Distinguisable 

(q1,q2) → Indistinguishable 

(q1,q3) → Distinguisable  

(q1,q4) → Distinguisable 

(q2,q3) → Distinguisable 

(q2,q4) → Distinguisable 

(q3,q4) → Indistinguishable

Setelah semua pasangan state telah dipasangkan dengan setiap input yang ada maka terdapat state-state yang Distinguishable yaitu : 

(q0,q1) 

(q0,q2) 

(q0,q3) 

(q0,q4) 

(q1,q3)

(q1,q4)

(q2,q3) 

(q2,q4) 

Karena berdasarkan relasi-relasi yang ada, tidak dapat dibuktikan (q1, q2)dan (q3, q4) distinguishable, sehingga disimpulkan pasangan-pasangan state tersebut indistinguishable. 

5. Karena q1 indistinguishable dengan q2, 

q3 indistinguishable dengan q4, 

maka dapat disimpulkan q1, q2 dan q3, q4 saling indistinguishable dan dapat dijadikan satu state. 

Berdasarkan hasil diatas maka hasil dari DFA yang direduksi menjadi :