NFA Dengan ε - Move

 

• 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 :

  1. BuattabeltransisiNFAε–movesemula 
  2. Tentukanε_closureuntuksetiapstate 
  3. Carilah setiap fungsi transisi hasil perubahan dari NFA ε – move ke
     NFA tanpa ε – move (disebut dengan δ’) dimana δ’ didapatkan dengan rumus :
     δ’(state, input) = ε_closure(δ(ε_closure(state),input)) 
  4. Berdasarkan hasil no 3, kita bisa membuat tabel transisi dan diagram transisi dari NFA tanpa ε – move yang ekivalen dengan NFA ε –
     move tersebut. 
  5. Tentukan state-state akhir, yaitu dengan cara menambahkan state-
     state akhir semula ditambah dengan state-state yang ε-closure-nya menuju kesalah satu dari state akhir semula. Dalam bahasa formalnya : F’ = F U {q І (ε_closure(q) ∩ F)≠Ф } 

  
  

  Contoh : NFA ε – move

  
  

  

  
  

  1. Tabel Transisi untuk NFA ε – move diatas adalah : δab

  q0 {q0} q1 Ø q2 Ø

  
  

  2. Tentukan ε_closure untuk setiap state : 

  ε_cl(q0)={q0,q1}
  ε_cl(q1)={ q1}
  ε_cl(q2)={q0,q1,q2}

  
  

  3. Tentukan δ’ :
  δ’(q0,a)  = ε_closure(δ(ε_closure(q0),a))

  = ε_closure(δ({q0,q1}, a)) 

  = ε_closure(q0)
  = {q0,q1}

  δ’(q0,b)  = ε_closure(δ(ε_closure(q0),b)) 

  = ε_closure(δ({q0,q1}, b))

  = ε_closure(q2) = {q0,q1,q2}

  δ’(q1,a)   = ε_closure(δ(ε_closure(q1),a)) 

  = ε_closure(δ({q1}, a))

  = ε_closure(Ø)

  =Ø
  δ’(q1,b)   = ε_closure(δ(ε_closure(q1),b))

  = ε_closure(δ({q1}, b)) 

  = ε_closure(q2)
  = {q0,q1,q2}

  δ’(q2,a)  = ε_closure(δ(ε_closure(q2),a)) 

  = ε_closure(δ({q0,q1,q2}, a))

  = ε_closure(q0)

  = {q0,q1}
  δ’(q2,b)  = ε_closure(δ(ε_closure(q2),b))

  = ε_closure(δ({q0,q1,q2}, b)) 

  = ε_closure(q2)
  = {q0,q1,q2}

  
  

  4. Tabel transisi dari hasil no.3 yaitu NFA tanpa ε – move δab

  
  

  

  
  

  5. Himpunan State akhir dari NFA tanpa ε – move
  ♦ Himpunan State akhir semula adalah {q0}
  ♦ State-state yang ε_closure-nya menuju ke salah satu dari state

  akhir semula adalah ε_closure(q2)0={q0,q1,q2}. Sehingga himpunan state akhir sekarang / F’= {q0,q2}

  
  

  6. Diagramtransisi dari NFA tanpa ε–move adalah sebagai berikut:

  
  

  
  
  

  
  

•