Ekuivalensi NFA ke DFA
Dari sebuah mesin Non-deterministic Finite Automata dapat dibuat mesin Deterministic Finite Automata-nya yang ekuivalen.Ekuivalen disini artinya menerima bahasa yang sama .Meskipun yang satu adalah Non-deterministic dan yang satunya Deterministic namun keduanya menerima bahasa yang sama.
Sasaran : mengurangi Jumlah State dari FSA dengan tidak mengurangi kemampuannya untuk menerima suatu bahasa.
 |
| Image source : https://makasihmantans.blogspot.co.id/2018/04/ekuivalensi-antara-dfa.html |
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 dari FSA yang direduksi merupakan ekuivalensi dari FSA semula
Note :
a. Useless : tidak memberi/menerima inputan siapa-siapa tapi punya output.
b. Apabila dari proses didapat hasil berikut,maka:
Dist + Dist = Indist
Indist + Dist = DIst
State Final Ketemu State FInal = Indist
Contoh soal beserta jawaban :
Itulah tadi informasi yang dapat saya berikan. Selamat membaca, dan terima kasih atas kunjungannya.
Posting Komentar