Merubah NFA dengan E-Move ke NFA tanpa E – Move

-

 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, 14 Juni 2023, materi yang disampaikan adalah pembahasan tentang teori Merubah NFA dengan E-Move ke NFA tanpa E – Move


NFA Dengan E-Move

 

  • NFA dengan E-Move (transisi E-Move), diperbolehkan merubah state tanpa membaca input.
  • Disebut dengan E-Move karena tidak bergantung pada 1 input saat transisi. 

E-Move Berada Pada Transisi State

 

  • Sebuah transisi mempunyai input/output/E-Move
  • Suatu E-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


E-Closure

  • E- Closure adalah himpunan state yang dapat dicapai dari suatu state tanpa membaca input
  • E-Closure (q0) = himpunan state yang dapat dicapai dari state q0 tanpa membaca input 
  • Pada suatu state yang tidak memiliki E-Move, maka E-Closure nya adalah state itu sendiri

Contoh

 

Contoh, Diagram Transisi 1
















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

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

E – Closure (q2) = {q2}

E – Closure (q3) = {q3}

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


Merubah NFA dengan E-Move ke NFA tanpa E – Move













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
















2.     Cari E -Closure untuk setiap NFA 

 

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

E – Closure (q1) = {q1}

E – Closure (q2) = {q2}

E – Closure (q3) = {q3}



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

 

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

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

                        E- CL (q2)

                        {q2}

 

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

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

                        E- CL (q3)

                        {q3}

 

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

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

                        E- CL (q2)

                        {q2}

            

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

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

                        E- CL (q3)

                        {q3}

 

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

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

                        E- CL (empty)

                        {empty}

 

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

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

                        E- CL (empty)

                        {empty}

 

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

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

                        E- CL (empty)

                        {empty}

 

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

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

                        E- CL (empty)

                        {empty}

 

4.     Buat tabel transisi baru NFA  tanpa E-Move










5. Gambar diagram transisi baru NFA  tanpa E-Move













Berikut diatas merupakan ringkasan materi dan contoh soal dari  Merubah NFA dengan E-Move ke NFA tanpa E – Move

Pembahasaan materi pada 14 Juni 2023 . Sekian yang bisa saya sampaikan, Mohon maaf bila ada salah pengetikan.
Terimakasih, Sampai bertemu di penyampaian materi berikutnya👐😊

Wassalamualaikum Warrahmatullahi Wabarrakatuh



 



Komentar

Posting Komentar