Pertemuan 6 : Ekuivalensi NFA dengan ε - Move

Ekuivalensi NFA dengan ε - Move

NFA dengan ε-Move (transisi ε-Move), diperbolehkan merubah state tanpa membaca input. Disebut dengan ε-Move karena tidak bergantung pada 1 input saat transisi. ε-Move Berada Pada Transisi State Sebuah transisi mempunyai input/output/ ε-Move.

Suatu ε-Move untuk state q1 dan q2 yang terhubung dapat berpindah tanpa menghasilkan inputan apapun pada transisinya. Contoh :

 

Tanpa membaca input :

q0 dapat berpindah ke q

q1 dapat berpindah ke q2

q4 dapat berpindah ke q1

ε-Closure

ε-Closure adalah himpunan state yang dapat dicapai dari suatu state tanpa membaca input

ε-Closure (q0) = himpunan state yang dapat dicapai dari state q0 tanpa membaca input 

Pada suatu state yang tidak memiliki ε-Move, maka ε-Closure nya adalah state itu sendiri

Contoh, Diagram Transisi 1 

ε - Closure (q0) = {q0,q1,q2}

ε - Closure (q1) = {q1,q2}

ε – Closure (q2) = {q2}

ε – Closure (q3) = {q3}

ε – Closure (q4) = {q4,q1,q2}

Merubah NFA dengan E-Move ke NFA tanpa Ε-move

1.     Buat table transisi NFA ε-Move dari diagram NFA semula 

2.     Cari ε - Closure untuk setiap NFA  

ε - Closure (q0) = {q0,q1}

ε – Closure (q1) = {q1}

ε – Closure (q2) = {q2}

ε – Closure (q3) = {q3}

3. Cari setiap fungsi transisi hasil perubahan dari NFA ke E-Move ke NFA tanpa E-Move, dengan rumus 

δ’ (q0,a) = ε - CL (δ (E- CL (q0), a)

                  ε - CL (δ (E- CL (q0,q1), a)

                  ε - CL (q2)

                  {q2}

δ’ (q0,b) = ε - CL (δ (E- CL (q0), b)

                  ε - CL (δ (E- CL (q0,q1), b)

                  ε - CL (q3)

                  {q3}

δ’ (q1,a) = ε - CL (δ (E- CL (q1), a)

                  ε - CL (δ (E- CL (q1), a)

                  ε - CL (q2)

                  {q2}

δ’ (q1,b) = ε - CL (δ (E- CL (q1), b)

                  ε - CL (δ (E- CL (q1), b)

                  ε - CL (q3)

                  {q3}

δ’ (q2,a) = ε - CL (δ (E- CL (q2), a)

                  ε - CL (δ (E- CL (q2), a)

                  ε - CL (empty)

                  {empty}

d’ (q2,b) = ε - CL (d (E- CL (q2), b)

                  ε - CL (d (E- CL (q2), b)

                  ε - CL (empty)

                  {empty}

d’ (q3,a) = ε - CL (d (E- CL (q3), a)

                  ε - CL (d (E- CL (q3), a)

                  ε - CL (empty)

                  {empty}

d’ (q3,b) = ε - CL (d (E- CL (q3), b)

                  ε - CL (d (E- CL (q3), b)

                  ε - CL (empty)

                  {empty}

4.     Buat tabel transisi baru NFA tanpa ε - Move

5. Gambar diagram transisi baru NFA  tanpa ε - Move

Berikut diatas merupakan ringkasan materi dan contoh soal dari  Merubah NFA dengan ε-move ke NFA tanpa ε-move.


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