Non Deterministic Finite Automata (NFA) ke E-Move

    Suatu gambar Non-Deterministc Finite Automata (NFA) yang mengandung ε-Move ( ε dapat dianggap “empty” artinya dapat tidak dibaca inputannya atau diperbolehkan langsung menuju state berikutnya tanpa membaca inputan ε). 

Contoh gambar Non-Deterministic Finite Automata mengandung ε-Move :

Berdasarkan gambar diatas maka dapat di ambil kesimpulan : 

- Dari q0 tanpa membaca input dapat langsung berpindah ke state q1 

- Dari q2 tanpa membaca input dapat langsung berpindah ke state q3 

Kegunaan transisi ε ini adalah memudahkan dalam mengkombinasikan Finite State Automata.

ε – Clouser untuk suatu Non-Deterministic Finite Automata dengan ε-Move 

ε–closure merupakan himpunan state-state yang dapat dicapai dari suatu state tanpa membaca input. ε–closure sendiri dapat disingkat nantinya menjadi ε–cl. Contoh pada gambar berikut :

Langkah-langkah ε – Clouser untuk suatu Non-Deterministic Finite Automata dengan ε-Move :

1. Buat tabel transisi Non-Deterministic Finite Automata yang mengandung ε – Move 

2. Tentukan ε- closure untuk setiap state

ε–closure (q0) = {q0,q1} 

ε–closure (q1) = {q1} 

ε–closure (q2) = {q2,q3} 

ε–closure (q3) = {q3}  

3. Carilah setiap fungsi transisi hasil perubahan Non-Deterministic Finite Automata ε – Move ke Non-Deterministic Finite Automata tanpa ε – Move dengan menggunakan rumus : 

- δ' (q0,0) = ε – cl ( δ (ε – cl (q0),0)) 

                    ε – cl ( δ{q0,q1},0) 

                    ε – cl ({q2}) 

                    { q2,q3}

- δ' (q0,1) = ε – cl ( δ (ε – cl (q0),1)) 

                    ε – cl ( δ{q0,q1},1) 

                    ε – cl ({}) 

                    { }

- δ' (q1,0) = ε – cl ( δ (ε – cl (q1),0)) 

                    ε – cl ( δ{q1},0) 

                    ε – cl ({q2}) 

                    {q2,q3}

- δ' (q1,1) = ε – cl ( δ (ε – cl (q1),1)) 

                    ε – cl ( δ{q1},1) 

                    ε – cl ({}) 

                    { }

- δ' (q2,0) = ε – cl ( δ (ε – cl (q2),0)) 

                    ε – cl ( δ{q2,q3},0) 

                    ε – cl ({q3}) 

                    {q3} 

- δ' (q2,1) = ε – cl ( δ (ε – cl (q2),1)) 

                    ε – cl ( δ{q2,q3},1) 

                    ε – cl ({q1}) 

                    {q1}

- δ' (q3,0) = ε – cl ( δ (ε – cl (q3),0)) 

                    ε – cl ( δ{q3},0) 

                    ε – cl ({q3}) 

                    {q3}

- δ' (q3,1) = ε – cl ( δ (ε – cl (q3),1)) 

                    ε – cl ( δ{q3},1) 

                    ε – cl ({q1}) 

                    {q1} 

4. Buat table transisi baru dari hasil perolehan yang sudah dilakukan pada point(3) 

5. Tentukan Final State dengan melihat state-state pada ε –closure yang menuju pada state finish semula

Finis semula ada di q3, sehingga lihat state ε –closure yang menuju pada state q3 

ε–closure (q0) = {q0,q1} 

ε–closure (q1) = {q1} 

ε–closure (q2) = {q2,q3} 

ε–closure (q3) = {q3} 

Berdasarkan ε–closure diatas maka dapat diperoleh state Finish lain selain q3 yaitu q2, sehingga final state sekarang ada 2 yaitu state q2 dan state q3. 

Gambar Non-Deterministic Finite Automata tanpa ε-Move :