NFA DENGAN E-MOVE

 Jenis otomata baru yang disebut Non-deterministic Finite Automata dengan ε -move( ε disini bisa dianggap sebagai empty). Pada Nondeterministic Finite Automata dengan ε -move (transisi ε ), diperbolehkan merubah state tanpa membaca input. Disebut dengan transisi ε  karena tidak bergantung pada suatu inout ketika melakukan transisi. 

Perhatikan gambar berikut!

Penjelasan:

ε 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 memudahkan kita untuk mengkombinasikan finite state automata.

ε-Closure untuk NFA ε-Move

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

ε-closure dari state diatas adalah:

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

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

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

ε-closure (q3) = {q3} 

ε-closure (q4) = {q4}

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

Ekuivalensi NFA ε-move ke NFA tanpa ε-move

Dari sebuah Non-deterministic Finite Automata dengan ε-move dapat kita peroleh Non- deterministic Finite Automata tanpa ε-move yang ekuivalen.

Gambar di bawah ini menunjukkan hasil akhir NFA tanpa ε-move yang ekivalen dengan NFA ε-move