Pertemuan 5 : Ekuivalensi NFA ke DFA

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 tersebut 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}.

·                State {q0} bila memperoleh input 1 menjadi state {q1}.

Ekuivalensi Non-Deterministic Automata (NFA)  ke Deterministic Finite Automata (DFA)

·                State {q1} memperoleh input 0 menjadi state ∅

·                State {q1} bila memperoleh input 1 menjadi state {q0, q1}.

Pada state {q0,q1} pada awalnya masih belum mempunyai busur dan pada DFA,sebuah state harus mempunyai busur sama banyak dengan himpunan inputnya, karena itu kita tentukan terlebih dahulu arah busurnya dan busurnya ada 2.

δ({q0,q1},0)  = {q0,0} ε {q1,0}

          = {q0,q1} ε Ø

          = {q0,q1}

δ({q0,q1},1) = {q0,1} ε {q1,1}

          = {q1} ε {q0,q1}

          = {q0,q1}

Jadi arah busur pada state {q0,q1} mengarah ke state itu sendiri.

Kemudian khusus pada state himpunan kosong (Ø) hanya menerima inputan dari statenya sendiri,jadi busur pada himpunan kosong mengarah ke state himpunan kosong.


Ekuivalensi Non-Deterministic Automata (NFA)  ke Deterministic Finite Automata (DFA)

Terakhir untuk menentukan final state pada DFA ini adalah dengan melihat NFA yang ekuivalen dengan DFA ini yaitu soal awal,

Kita ketahui Bahwa final state adalah q1,jadi pada DFA,final statenya adalah semua state yang ada hubungannya dengan q1 yaitu {q0,q1} dan {q1}

Ekuivalensi Non-Deterministic Automata (NFA)  ke Deterministic Finite Automata (DFA).

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