Ekuivalensi Antar Deterministic Finite Automata (DFA)

"Ekuivalensi Antar Deterministic Finite Automata (DFA)"

Sasaran kita di sini 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.

Reduksi Jumlah State Pada FSA

Reduksi dilakukan untuk mengurangi jumlah state tanpa mengurangikemampuan 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.      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

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 eveluasi state, didefinisikan suatu relasi : Untuk Q yg merupakan himpunan semua state

• D adalah himpunan state-state distinguishable, dimana D Ì Q

• N adalah himpunan state-state indistinguishable, dimana N Ì Q Dine Tiara Kusuma

• maka x Î N jika x Î Q dan x Ï D

Contoh Soal :