NDFA dengan ε-Move

Pada materi ini kita akan membahas tentang ε-closure dan ekivalensi. ε disini bisa dianggap sebagai empty. Pada NDFA dengan ε-move (transisi ε) diperbolehkan merubah state tanpa membaca input. Disebut dengan transisi ε karena tidak tergantung pada input ketika melakukan transisi.

Mesin NFA dengan ε-move Contoh 1

q0 tanpa input ke q1
q1 tanpa input ke q2
q4 tanpa input ke q1

Salah satu kegunaan transisi ε ini memudahkan kita mengkombinasaikan finite state automata.

ε-closure untuk suatu NDFA dengan ε-move

ε-closure adalah himpunan state-state yang dapat dicapai dari satu state tanpa membaca input.

Misalnya saja ε-closure (q0) = himpunan state-state yang dapat dicapai state q0 tanpa membaca input maka dengan melihat gambar 1. ε-closure (q0) = {q0,q1,q2}, artinya dari state q0 tanpa membaca input dapat mencapai state q0, q1 dan q2.

ε-closure untuk state lainnya bisa dilihat sebagai berikut:

ε-closure (q1) = {q1,q2}
ε-closure (q2) = {q2}
ε-closure (q3) = {q3}
ε-closure (q4) = {q1,q2,q4}

Mesin NFA dengan ε-move Contoh 2

ε-closure untuk state lainnya bisa dilihat sebagai berikut:

ε-closure (q0) = {q0,q1,q3}
ε-closure (q1) = {q1,q3}
ε-closure (q2) = {q2,q4}
ε-closure (q3) = {q3}
ε-closure (q4) = {q4}

Note: Pada state yang tidak memiliki transisi ε, maka ε-closurenya adalah state itu sendiri.

Ekivalensi NDFA dengan ε-move ke NDFA tanpa ε-move

Beberapa tahapan untuk mendapatkan perubahan NDFA ε-move ke NDFA tanpa ε-move

1. Buat table transisi NDFA ε-move semula
2. Tentukan ε-closure untuk setiap state
3. Carilah setiap fungsi transisi hasil perubahan dari NDFA ε-move ke NDFA tanpa ε-move rumusnya
   δ'(state,input) = ε-closure (δ(ε-closure (state),input))
4. Berdasarkan hasil no(3) kita dapat membuat tabel transisi dan diagram transisi dari NDFA ε-move yang ekivalen dengan NDFA ε-move tersebut.
5. Tentukan state-state akhir untuk NDFA tanpa ε-move tersebut yaitu state-state akhir semula ditambah dengan state-state yang ε-closure nya menuju ke salah satu dari state akhir semula.

Kita coba lakukan:

Langkah 1:

Tabel transisi dari gambar 3 sebagai berikut:

δ	a	b
q0	∅	∅
q1	q2	q3
q2	∅	∅
q3	∅	∅

Langkah 2:

Menentukan ε-closure untuk setiap state (ε-closure bisa kita singkat ε-cl)

ε-cl (q0) = {q0,q1}
ε-cl (q1) = {q1}
ε-cl (q2) = {q2}
ε-cl (q3) = {q3}

Langkah 3:

Kemudian kita cari δ’ dengan memanfaatkan tabel transisi dan ε-closure yang kita peroleh sebelumnya sebagai berikut:

δ’ (q0,a) = ε-closure (δ(ε-closure(q0,a))
                = ε-closure (δ({q0,q1},a))
                = ε-closure (q2)
                = {q2}

δ’ (q0,b) = ε-closure (δ(ε-closure(q0,b))
                = ε-closure (δ({q0,q1},b))
                = ε-closure (q3)
                = {q3}

δ’ (q1,a)     = ε-closure (δ(ε-closure(q1,a))
                    = ε-closure (δ({q1},a))
                    = ε-closure (q2)
                    = {q2}

δ’ (q1,b)     = ε-closure (δ(ε-closure(q1,b))
                    = ε-closure (δ({q1},b))
                    = ε-closure (q3)
                    = {q3}

δ’ (q2,a)     = ε-closure (δ(ε-closure(q2,a))
                    = ε-closure (δ({q2},a))
                    = ε-closure (∅)
                    = ∅

δ’ (q2,b)     = ε-closure (δ(ε-closure(q2,b))
                    = ε-closure (δ({q2},b))
                    = ε-closure (∅)
                    = ∅

δ’ (q3,a)     = ε-closure (δ(ε-closure(q3,a))
                    = ε-closure (δ({q3},a))
                    = ε-closure (∅)
                    = ∅

δ’ (q3,b)     = ε-closure (δ(ε-closure(q3,b))
                    = ε-closure (δ({q3},b))
                    = ε-closure (∅)
                    = ∅

Maka kita akan mendapatkan tabel transisi dari NFA tanpa ε-move dari hasil diatas:

δ	a	b
q0	q2	q3
q1	q2	q3
q2	∅	∅
q3	∅	∅