NFA DENGAN ε - MOVE

Non-deterministic Finite Automata (NFA) Dengan ε-Move

note d = teta

Di sini kita mempunyai jenis otomata baru yang disebut Non-deterministic Finite Automata dengan ε-move (ε-move disini bisa dianggap sebagai ‘empty’). Pada NFA dengan ε-move (transisi ε), diperbolehkan merubah state tanpa membaca input. Disebut dengan transisi ε karena tidak bergantung pada suatu input ketika melakukan transisi.
Contoh:

·         Dari q0 tanpa membaca input dapat berpindah ke q1
·         Dari q1 tanpa membaca input dapat berpindah ke q2
·         Dari q4 tanpa membaca input dapat berpindah ke q1
Salah satu kegunaan dari transisi ε ini adalah memudahkan kita untuk mengkombinasikan Finite State Automata.
ε-Closure untuk Suatu Non-deterministic Finite Automata (NFA) dengan ε-Move

ε-Closure adalah himpunan state-state yang dapat dicapai dari suatu state tanpa membaca input. Misalkan saja ε-closure(q0) = himpunan state-state yang dapat dicapai dari state q0 tanpa membaca input.Maka dengan melihat contoh diatas ε-closure(q0) = { q0, q1, q2}, artinya dari state q0 tanpa membaca input dapat mencapai state q0, q1, q2.
ε-closure(q0) = { q0, q1, q2},
ε-closure(q1) = { q1, q2},
ε-closure(q2) = { q2},
ε-closure(q3) = { q3},
ε-closure(q4) = { q1, q2, q4}
*Perhatikan: Pada suatu state yang tidak memiliki transisi ε, maka ε-closure-nya adalah state itu sendiri.
Ekivalensi NFA dengan ε-Move ke NFA tanpa ε-Move 

    Dari sebuah NFA dengan ε-move dapat kita peroleh NFA tanpa ε-move yang ekivalen.
Contoh:

Tabel transisi dari NFA ε-move diatas adalah:

State akhir (F) adalah state q3
ε-closure untuk setiap state nya:
ε-closure(q0) = { q0, q1},
ε-closure(q1) = { q1},
ε-closure(q2) = { q2},
ε-closure(q3) = { q3}
kemudian kita cari d’ dengan memanfaatkan tabel transisi dan ε-closure yang kita peroleh sebelumnya,sebagai berikut:
d’ (q0,a) = ε-closure (δ(ε-closure (q0),a))
              = ε-closure (δ ({ q0, q1},a))
              = ε-closure (q2)
              = {q2}
d’ (q0,b) = ε-closure (δ(ε-closure (q0),b))
              = ε-closure (δ({ q0, q1},b))
              = ε-closure (q3)
              = {q3}
d’ (q1,a) = ε-closure (δ(ε-closure (q1),a))
              = ε-closure (δ({ q1},a))
              = ε-closure (q2)
              = {q2}
d’ (q1,b) = ε-closure (δ(ε-closure (q1),b))
              = ε-closure (δ({q1},b))
              = ε-closure (q3)
              = {q3}
d’ (q2,a) = ε-closure (δ(ε-closure (q2),a))
              = ε-closure (δ({q2},a))
              = ε-closure (θ)
              = θ
d’ (q2,b) = ε-closure (δ(ε-closure (q2),b))
              = ε-closure (δ({q2},b))
              = ε-closure (θ)
              = θ
d’ (q3,a) = ε-closure (δ(ε-closure (q3),a))
              = ε-closure (δ({ q3},a))
              = ε-closure (θ)
              = θ
d’ (q3,b) = ε-closure (δ(ε-closure (q3),b))
              = ε-closure (δ({ q3},b))
              = ε-closure (θ)
              = θ
Bisa kita lihat tabel transisi untuk NFA tanpa ε-move dari hasil di atas:

 Terakhir kita tentukan state akhir untuk NFA tanpa ε-move ini. Himpunan state akhir semula adalah {q3}.Karena tidak ada state lain yang ε-closurenya memuat q3, maka himpunan state akhir sekarang tetap {q3}.
 SEDIKIT CONTOH SOALNYA