Teori Bahasa dan Automata

  Ekuivalensi Antar Deterministic Finite Automata (DFA)          Tujuan kita adalah mengurangi jumlah state dari suatu finite state automata, dengan tidak mengurangi kamampuannya semula untuk menerima suatu bahasa.  Ada 2 istilah yang perlu kita ketahui yaitu : Distinguishable : dapat dibedakan Indistinguishable : tidak dapat dibedakan Reduksi Jumlah State Pada FSA         Reduksi dilakukan untuk mengurangi jumlah state tanpa mengurangi kemampuan untuk menerima suatu bahasa seperti semula (efisiensi). State pada FSA dapat direduksi apabila terdapat  useless state .  Useless State  yaitu bukan state awal, tidak menerima nilai input dari state lain tetapi memberikan nilai input ke state lain. Hasil dari FSA yang direduksi merupakan ekuivalensi dari FSA semula. Pasangan State dapat dikelompokkan berdasarkan :  Distinguishable State (dapat dibedakan) Indistingushbale (tidak dapat dibedakan) Reduksi Jumlah State Pada FSA - Relasi         Pasangan dua buah state memiliki satu kemungkinan :