Pertemuan 4 : Ekuivalensi DFA (Deterministic Finite Automata)
Ekuivalensi Antar Deterministic Finite Automata Tujuan ekuivalensi ini untuk mengurangi jumlah state dari suatu FSA (Finite State Automata), dengan tidak mengurangi kemampuannya semula untuk menerima suatu Bahasa. Ekuivalen sendiri merupakan persamaan dari sebanding, sepadan, dan seharga. Ada 2 buah istilah baru yang perlu diketahui yaitu : · Distinguishable yang berarti dapat dibedakan. · Indistinguishable yang berarti tidak dapat dibedakan. Reduksi jumlah state pada FSA Reduksi digunakan untuk mengurangi jumlah state tanpa perlu mengurangi kemampuan untuk menerima suatu Bahasa seperti semula (efisien) State pada FSA dapat direduksi bila terdapat useless state. Hasil FSA yang sudah direduksi dapat disebut ekuivalensi dari FSA semula Distinguished State · Dua state p dan q dari suatu DFA dikatakan Indistinguishable apabila :...