E-Learning TBO

  Pada NFA dengan ε – move (transisi ε ) diperbolehkan merubah state tanpa membaca input . ♦  Dikatakan dengan transisi ε karena tidak bergantung pada suatu input ketika melakukan transisi. Contoh : Penjelasan :  ♦ Dari q1 tanpa membaca input dapat berpindah ke q2  ε _ closure untuk Suatu NFA dengan ε – Move ♦ ε _ closure adalah himpunan state-state yang dapat dicapai dari suatu state tanpa membaca input . Contoh :  Penjelasan : ε _ closure dari NFA dengan ε – move diatas untuk setiap state adalah : ε_closure(q0) ε_closure(q1) ε_closure(q2) ε_closure(q3) ε_closure(q4) Perhatikan : ε_closure-nya adalah state itu sendiri. Ekivalensi NFA dengan ε – Move ke NFA dengan Tanpa ε – Move Langkah – langkah : BuattabeltransisiNFAε–movesemula  Tentukan ε_closure untuksetiap state  Carilah setiap fungsi transisi hasil perubahan dari NFA ε – move ke NFA tanpa ε – move (disebut dengan δ’) dimana δ’ didapatkan dengan rumus : δ’( state, input ) = ε_clos...

Sebuah diagram NFA dapat dikonversi menjadi DFA dengan membuat table transisi yang baru berdasarkan analisa dari transisi pada NFA. Perhatikan contoh berikut ini. Jika diberikan sebuah NFA seperti pada gambar diatas dengan X1 sebagai state awal (Start state) dan X6 sebagai state akhir (final state). Alphabet yang digunakan pada NFA tersebut adalah {1,2} dan berikut ini adalah tabel transisi dari diagram tersebut. State 1 2 -> X1 {X2, X3} X5 X2 X3 {X3, X4} X3 X6 X4 X4 X4 X6 X5 X5 {X5, X6} *X6 – – Biasanya pada tabel transisi untuk menandakan sebuah start state diberikan dengan tanda panah, dan untuk final state ditandakan dengan tanda *. Setelah kita mengetahui tabel transisi dari NFA maka kita akan membuat tabel transisi dari DFA tersebut. Pada awalnya start state pada DFA  akan sama dengan start state di NFA, yaitu X1. Kita lihat bahwa transisi dari state X1 jika diberikan input 1 maka akan men...