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 :

·         δ (q,w) Î F dan  δ (p,w) Î F atau δ (q,w) ∉ F dan δ (p,w) ∉ F

·         untuk semua w Î S*

Indistinguished State

·         Dua state p dan q dari suatu DFA dikatakan distinguishable jika ada string w Î S* hingga :

·        δ (q,w) Î F dan  δ (p,w) ∉ F

Pasangan dua 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,   r  indistinguishable dan

 p,q,r indistinguishable


Contoh reduksi state pada suatu 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 Î F sedang q0, q1, q2, q3 ÏF sehingga pasangan-pasangan state :

(q0,q1)

(q0,q2)

(q0,q3)

(q0,q4)

(q1,q2)

(q1,q3)

(q1,q4)

(q2,q3)

(q2,q4)

(q3,q4)

Selanjutnya menjadi :

(q0,q1)

(q0,q2)

(q0,q3)

(q0,q4) à Distinguishable

(q1,q2)

(q1,q3)

(q1,q4) à Distinguishable

(q2,q3)

(q2,q4) à Distinguishable

(q3,q4) à Distinguishable

Lalu : Cari Status Pasangan lainnya, dengan memperhatikan inputan yang tersedia yaitu 0 dan 1 :

·         Pasangan (q0,q1)

- δ (q0, 0) = q1 dan δ (q1, 0) = q2

➔ (q1 ,q2) belum terdefinisi

- δ (q0,1) = q3 dan δ(q1, 1) = q4

➔ (q3 ,q4) Distinguisable

Maka (q0, q1) adalah Distinguishable

(q0,q1) à Distinguishable

(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 (q1,q2)

-          δ (q1, 0) = q2 dan δ (q2, 0) = q1

➔ (q2 ,q1) belum terdefinisi

-          δ (q1, 1) = q3 dan δ (q2, 1) = q4

➔ (q3 ,q4) Distinguisable

Maka (q0, q2) adalah Distinguishable

(q0,q1) à Distinguishable

(q0,q2) à Distinguishable     

(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,q3)

-          δ (q0, 0) = q1 dan δ (q3, 0) = q2

➔ (q1 ,q2) belum terdefinisi

-          δ (q0, 1) = q3 dan δ (q3, 1) = q4

➔ (q3 ,q4) Distinguisable

Maka (q0, q3) adalah Distinguishable

(q0,q1) à Distinguishable

(q0,q2) à Distinguishable     

(q0,q3) à Distinguishable

(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 (q1,q2) :

-          δ (q1, 0) = q2 dan δ (q2, 0) = q1

➔ (q2 ,q1) belum terdefinisi

-          δ (q1, 1) = q4 dan δ (q2, 1) = q4

➔ (q4 ,q4) belum terdefinisi

Maka (q1, q2) adalah belum terdefinisi

 

Pasangan (q1,q3) :

-          δ (q1, 0) = q2 dan δ (q3, 0) = q2

➔ (q2, q2) belum terdefinisi

-          δ (q1, 1) = q4 dan δ (q3, 1) = q4

➔ (q4, q4) belum terdefinisi

Maka (q1, q2) adalah belum terdefinisi

 

Pasangan (q2,q3) :

-          δ (q2, 0) = q1 dan δ (q3, 0) = q2

➔ (q1, q2) belum terdefinisi

-          δ (q2, 1) = q4 dan δ (q3, 1) = q4

➔ (q4, q4) belum terdefinisi

Maka (q1, q2) adalah belum terdefinisi

 

(q0,q1) à Distinguishable

(q0,q2) à Distinguishable     

(q0,q3) à Distinguishable

(q0,q4) à Distinguishable

(q1,q2) à belum terdefinisi

(q1,q3) à belum terdefinisi

(q1,q4) à Distinguishable

(q2,q3) à belum terdefinisi

(q2,q4) à Distinguishable

(q3,q4) à Distinguishable 

Karena, pada pasangan (q1,q2), (q1,q3), dan (q2,q3) belum terdefinisi hingga akhir,maka ketiganya termasuk indistinguishable.

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:


Komentar

Posting Komentar

Postingan populer dari blog ini

Sejarah dan Perkembangan Prosesor Intel

Pendahuluan Prosesor Intel, perusahaan teknologi ternama yang berdiri pada tahun 1968 oleh Gordon Moore dan Robert Noyce, telah menjadi tonggak utama dalam evolusi komputasi modern. Dari prosesor awal yang sederhana hingga teknologi canggih saat ini, Intel telah memimpin inovasi dalam desain dan kinerja prosesor. Prosesor Awal: Dari Intel 4004 ke Intel 8086 Intel 4004 (1971): Prosesor 4-bit pertama di dunia, yang menandai awal dari revolusi mikroprosesor. Intel 8086 (1978): Membawa arsitektur x86 yang menjadi standar industri, memberikan fondasi bagi komputasi modern. Era 32-bit dan Pentium Intel 80386 (1985): Prosesor 32-bit pertama, membuka era baru dalam kinerja dan kemampuan komputasi. Pentium (1993): Sebuah tonggak dalam sejarah komputasi, Pentium menjadi salah satu produk paling ikonik dan sukses dari Intel. Perkembangan Kinerja: Dari Pentium ke Core Pentium II, III, dan IV: Terus meningkatkan kinerja dengan inovasi seperti arsitektur superskalar dan hyper-threading. Core Series ...
Baca selengkapnya

Mengenal ESP & ARDUINO serta Penerapannya dalam IoT

Gambar
Apa itu ESP? ESP adalah singkatan dari "Espressif Systems Platform", yang mengacu pada serangkaian mikrokontroler yang dikembangkan oleh perusahaan Espressif Systems, terutama ESP8266 dan ESP32. Mikrokontroler ESP ini populer karena kemampuannya untuk terhubung dengan jaringan Wi-Fi atau Bluetooth, yang membuatnya sangat cocok untuk pengembangan aplikasi Internet of Things (IoT) dan berbagai proyek elektronik yang memerlukan konektivitas nirkabel. Mikrokontroler ESP ini biasanya diprogram menggunakan bahasa pemrograman yang mirip dengan C/C++.   Apa itu Arduino? Arduino adalah sebuah platform perangkat keras dan perangkat lunak yang terbuka dan mudah digunakan untuk membuat berbagai proyek elektronik. Pada intinya, Arduino terdiri dari papan mikrokontroler yang dapat diprogram menggunakan bahasa pemrograman yang mirip dengan C/C++. Arduino menyediakan lingkungan pengembangan terpadu (IDE) yang sederhana untuk menulis kode, mengunggahnya ke papan Arduino, dan mengontro...
Baca selengkapnya

Pertemuan 5 : Ekuivalensi NFA ke DFA

Gambar
Ekuivalensi NFA ke DFA Ekuivalensi Non-Deterministic Finite Automata ke Deterministic Finite Automata 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. Contoh  : Sebagai contoh, akan dibuat Deterministic Finite Automata dari Non-Deterministic Finite Automata sebagai berikut : diketahui  Ʃ  : {0,1} Maka tabel transisinya adalah sebagai berikut : Kedua kita buat tuple dari tabel ters e but agar lebih detail δ  = {q0 , q1} Ʃ = {0 , 1} s =  q0 f =  q1 Lalu kita mulai membuat DFA nya Dimulai dari state awal q0 ·                  State {q0} bila memperoleh input 0 menjadi state {q0, q1}. ·          ...
Baca selengkapnya