Ekuivalensi Antar Deterministic Finite Automata
Asssalamualaikum Warrahmatullahi Wabarrakatuh
Halo semuaa !!.....👋😊
Selamat datang di blog saya, perkenalkan saya Rina Setiyaningsih dengan NIM 202131022 , Mahasiswi Informatika dan berkuliah di Institut Teknologi PLN Jakarta.
Disini saya akan membahas ulang materi yang sudah disampaikan Bu DINE TIARA KUSUMA ,S.T., M.Kom. pada pertemuan di hari Rabu,10 mei 2023, materi yang disampaikan adalah pembahasan tentang Ekuivalensi Antar Deterministic Finite Automata.
Ekuivalensi Antar Deterministic Finite 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
· Indistingushable
Yang berarti tidak dapat dibedakan.
Ekuivalensi Antar Deterministic Finite Automata
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
- Hasil dari FSA yang direduksi merupakan ekivalensi dari FSA semula
Pasangan state dapat dikelompokkan berdasarkan
Distinguishable
(dapat dibedakan)
Indistinguishable
(tidak dapat dibedakan)
Reduksi Jumlah State Pada FSA- relasi
Pasangan dua buah state memilik salah satu kemungkinan:
Distinguishable atau indistinguishable:
Tetapi tidak kedua-duanya. Dalam hal ini terdapat relasi :
Jika p dan q indistinguishable,
Dan p dan r indistinguishable
Maka p,r indistinguishable dan
p,q,r. indistinguishable
dalam melakukan evaluasi state, didefinisikan suatu relasi : untuk Q yg merupakan himpunan semua state
Sebuah mesin DFA
Reduksi Jumlah State pada FSA – Step
· State q5 tidak dapat dicapai dari state awal dengan jalan apapun (useless state). Hapus state q5
· Catat state-state distinguishable, yaitu:
q4 elemen F sedang q0,q1,q2 bukan elemen F sehingga pasangan
pasangan state :
(q0,q1)
(q0,q2)
(q0,q3)
(q0,q4) = distinguishable
(q1,q2)
(q1,q3)
(q1,q4) = distinguishable
(q2,q3)
(q2,q4) = distinguishable
(q3,q4) = distinguishable
Cari status pasangan lainnya, dengan memperhatikan inputan yang tersedia yaitu 0 dan 1:
Pasangan (q0,q1)
o 0 > (q0,0) = q1 dan (q1,0) = q2
Þ (q1,q2 belum terdefinisi)
o 1 > (q0,1) = q3 dan (q1,1) = q4
Þ (q3,q4 distinguishable)
Maka (q0,q1) adalah distinguishable
Pasangan(q0,q2)
o 0 > (q0, 0) = q1 dan (q2,0) = q1
Þ (q1,q1 belum terdefinisi)
o 1 > (q0,1) = q3 dan (q2,1) = q4
Þ (q3,q4 distinguishable)
Maka (q0,q2) adalah distinguishable
Pasangan (q0,q3)
o 0 > (q0,0) = q1 dan (q3,0) = q2
Þ (q1,q2 belum terdefinisi)
o 1 > (q0,1) = q3 dan (q3,1) = q4
Þ (q3,q4 distinguishable)
Maka (q0,q3) adalah distinguishable
Pasangan (q1,q2)
o 0 > (q1,0) = q2 dan (q2,0) = q1
Þ (q2,q1 belum terdefinisi)
o 1 > (q1,1) = q4 dan (q2,1) = q4
Þ (q4,q4 indistinguishable)
Maka (q1,q2) adalah indistinguishable
Pasangan (q1,q3)
o 0 > (q1,0) = q2 dan (q3,0) = q2
Þ (q2,q2 belum terdefinisi)
o 1 > (q0,1) = q3 dan (q3,1) = q4
Þ (q4,q4 indistinguishable)
Maka (q1,q3) adalah indisinguishable
Pasangan (q2,q3)
o 0 > (q2,0) = q1 dan (q3,0) = q2
Þ (q1,q2 belum terdefinisi)
o 1 > (q2,1) = q4 dan (q3,1) = q4
Þ (q4,q4 indistinguishable)
Maka (q2,q3) adalah indisinguishable
· pasangan state :
(q0,q1) = distinguishable
(q0,q2) = distinguishable
(q0,q3) = distinguishable
(q0,q4) = distinguishable
(q1,q2) = indistinguishable
(q1,q3) = indistinguishable
(q1,q4) = distinguishable
(q2,q3) = indistinguishable
(q2,q4) = distinguishable
(q3,q4) = distinguishable
· karena q1 indistinguishable dengan q2,
q1 indistinguishable dengan q3,
q2 indistinguishable dengan q3,
maka dapat disimpulkan q1,q2,q3 saling
indistinguishable dan dapat dijadikan satu state.
Berdasarkan hasil diatas maka hasil dari DFA yang direduksi menjadi
Wassalamualaikum Warrahmatullahi Wabarrakatuh
Komentar
Posting Komentar