Ekivalensi Antar DFA

Setelah kita mempelajari tentang DFA, pada kali ini kita akan mempelajari ekivalensi antar DFA. Bersama saya Sola, mari perhatikan materi ini:

Sasaran : Mengurangi jumlah state dari FSA, dengan tidak mengurangi kemampuannya semula untuk menerima sebuah bahasa.

Istilah yang digunakan :

• Distinguisable = dapat dibedakan
• Indistinguisable = tidak dapat dibedakan

Reduksi Jumlah State pada FSA :

• Reduksi dilakukan untuk mengurangi jumlah state tanpa mengurangi kemampuan untuk menerima suatu bahasa seperti semula.
• State pada FSA dapat direduksi apabila terdapat useless state.
• Hasil FSA yang direduksi merupakan ekivalensi dari FSA semula.

Keterangan : Useless state adalah state yang tidak menerima inputan dari manapun tetapi mengeluarkan output.

(q0,q1)

q0,0 -> q1 & q1,0 -> q1 => q1,q1 -> indistinguisable, sehingga dapat direduksi.

Contoh Soal 1 :

Penyelesaian :

Didapat State yang tidak useless : q0, q1, q2, q3, q4

• q0, q1 -> distinguisable
• q0, q2 -> distinguisable
• q0, q3 -> distinguisable
• q0, q4 -> distinguisable
• q1, q2 -> indistinguisable
• q1, q3 -> indistinguisable
• q1, q4 -> distinguisable
• q2, q3 -> indistinguisable
• q2, q4 -> distinguisable
• q3, q4 -> distinguisable

Pembuktian :

(q0, q1)

q0, 0 -> q1 & q1, 0 -> q2 =>q1, q2

q0, 1 -> q3 & q1, 1 -> q4 => q3, q4 = distinguisable

 

(q0, q2)

q0, 0 -> q1 & q2, 0 -> q1 =>q1, q1

q0, 1 -> q3 & q2, 1 -> q4 => q3, q4 = distinguisable

 

(q0, q3)

q0, 0 -> q1 & q3, 0 -> q1 =>q1, q1

q0, 1 -> q3 & q3, 1 -> q4 => q3, q4 = distinguisable

 

(q1, q3)

q1, 0 -> q2 & q3, 0 -> q2 =>q2, q2

q1, 1 -> q4 & q3, 1 -> q4 => q4, q4 = indistinguisable

 

(q1, q2)

q1, 0 -> q2 & q2, 0 -> q1 =>q1, q2

q1, 1 -> q4 & q2, 1 -> q4 => q4, q4 = indistinguisable

 

(q2, q3)

q2, 0 -> q1 & q3, 0 -> q2 =>q1, q2

q2, 1 -> q4 & q3, 1 -> q4 => q4, q4 = indistinguisable

jadi dapat direduksi menjadi :

Contoh soal 2 :

Lakukan reduksi terhadap state berikut:

Penyelesaian:

Maka state yang tidak useless didapat : q0, q1, q2, q3, q4

• q0, q1 -> distinguisable
• q0, q2 -> distinguisable
• q0, q3 -> distinguisable
• q0, q4 -> distinguisable
• q1, q2 -> indistinguisable
• q1, q3 -> distinguisable
• q1, q4 -> distinguisable
• q2, q3 -> distinguisable
• q2, q4 -> distinguisable
• q3, q4 -> indistinguisable

Pembuktian :

(q0, q1)

q0, 0 -> q1 & q1, 0 -> q2 =>q1, q2

q0, 1 -> q2 & q1, 1 -> q3 => q2, q3 = distinguisable

 

(q0, q2)

q0, 0 -> q1 & q2, 0 -> q2 =>q1, q2

q0, 1 -> q2 & q2, 1 -> q4 => q2, q4 = distinguisable

 

(q1, q2)

q1, 0 -> q2 & q2, 0 -> q2 =>q2, q2

q1, 1 -> q3 & q2, 1 -> q4 => q3, q4 = indistinguisable

sehingga dapat direduksi menjadi :

 

Dibuat Oleh Sola Gratia Pinandita Adi (201631181). Dilarang mengambil sebagian atau semua isi post ini  tanpa izin. Yang melanggar semoga mendapat balasan dari Yang Maha Kuasa. Nilai jelek mungkin? hehehe. Amin. 😀