Ekuivalensi Antar Deterministic Finite Automata - Tatabahasa dan Automata

 sasaran kita disini 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

dua state p dan q dari suatu DFA dikatakan indistinguishable apabila :

- indistinguishable, yang berarti tidak dapat dibedakan

dua state p dan q dari suatu DFA dikatakan distinguishable jika ada string :

reduksi jumlah state pada FSA 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 2 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 yang merupakan himpunan semua state.

- D adalah himpunan state - state distinguishable

- N adalah himpunan state - state indistinguishable

- maka :

contoh soal :

reduksi jumlah state pada FSA - step

state q5 tidak dapat dicapai dari state awal dengan jalan apapun (useless state). hapus state q5

pasangan state :

(qo,q1) ->disting

(q0,q2) ->disting

(q0,q3) ->disting

(q0,q4) ->disting

(q1,q2) ->indisting

(q1,q3) ->indisting

(q1,q4) ->disting

(q2,q3) ->indisting

(q2,q4) ->disting

(q3,q4) ->disting