NDFA dengan є–Move

Non Deterministic Finite Automata dengan є–Move
Non Deterministic Finite Automata dengan є –Move ( є disini bisa dianggap sebagai ’empty’). Pada Non–deterministic Finite Automata dengan є–move (transisi є ), diperbolehkan mengubah state tanpa membaca input. Disebut dengan transisi є karena tidak bergantung pada suatu input ketika melakukan transisi. 

Є-Closure untuk Suatu Non-Deterministic Finite Automata dengan Є–Move

Є-Closure adalah himpunan state-state yang dapat dicapai dari suatu state tanpa membaca input. Perhatikan gambar sebelumnya, maka diperoleh:

◦Є–Closure ( q0) = { q0, q1,q2 }

◦Є–Closure ( q1 ) = { q1, q2}

◦Є–Closure (q2 ) = { q2}

◦Є–Closure ( q3 ) = { q3}

◦Є–Closure ( q4) = { q1, q2, q4 }

Adapun tahap pengerjaannya :

1. Kita tentukan terlebih dahulu fungsi transisi dari graph soal diatas 
2. Tentukan Є–Closure (Є,CL) dimana Є,CL merupakan himpunan state yang dapat dicapai oleh Є-Move 
3. Cari setiap fungsi dari perubahan NFA Є-Move ke NFA tanpa Є-Move.  

Pengerjaannya seperti gambar dibawah ini :

Contoh lainnya :

Latihan soal :

Jawaban dan penyelesaiannya adalah :

1. Buatlah tabel transisi dari NFA є–move di atas. 
2. Tentukan є-closure untuk setiap state  
3. Carilah setiap fungsi transisi hasil dari pengubahan NFA є–move ke NFA tanpa є–move. Fungsi transisi itu ditandai dengan simbol δ’ 

4. Kemudian, tentukanlah himpunan state akhir untuk NFA tanpa є–move ini. Himpunan state akhir semula adalah {q0}. Kita lihat є_cl (q2) = {q0,q1,q2}, maka himpunan state akhir sekarang adalah {q0,q2}. Sehingga diperoleh diagram transisi sebagai berikut.

-SELESAI-