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.