Blog Teori Bahasa Dan Otomata tentang NON-DETERMINISTIC FINITE STATE AUTOMATA (NFA) DENGAN ε-Move || Siti Nurul Maghfirah L_ 202131125

                                                                      Institute Teknologi PLN Jakarta

                                                       Dosen : Dine Tiara Kusuma S.T., M.Kom

NFA Dengan E-Move

Disini kita mempunya outomata yang baru yang disebut NFA dengan ε-move (ε disini bisa dianggap sebagai ‘empaty’ atau kosong). Pada NFA dengan ε-move , diperbolehkan untuk mengubah state tanpa membaca input, atau bisa disebut juga dengan himpunan kosong atau hanya sebagai jembatan atara state satu dengan lainnya.

ε - Clousure untuk suatu NFA dengan ε – move

Sekarang kita akan menambahkan sebuah pengertian yaitu ε-closure. ε-closure adalah himpunan state-state yang dapat didapat dari suat state tanpa membaca inputan. Kita dapat melihat ε-closure yang dapat dicapai pada state pada gambar dibawah ini :

Pada gambar diatas dapat kita ketahui bahwa ε-closure untuk setiap state adalah sebagai berikut :

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

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

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

ε-closure(q3) = {q3}

ε-closure(q4) = {q4}

Catatan:

Perhatikan  bahwa  pada  suatu  state  yang  tidak  memiliki  transisi  e,  maka  e- closure-nya adalah state itu sendiri.

Ekuivalensi NFA dengan ε - Move ke NFA tanpa menggunakan ε – Move

Pada kali ini kita akan membahas bagi mana cara menghilangkan ε-move seperti yang telah kita ketahui diatas, seperti bagaimana menentukan ε-move dan ε-closure pada setiap state-state yang ada pada mesin NFA.

Dari sebuah NFA dengan ε-move kita dapat memperoleh NFA tampa ε-move yang ekuivalen. Seperti pada gamabar dibawah ini NFA dengan ε-move :

Dari model state diatas dapat kita peroleh sebuah mesin NFA tampa ε-move, tentu saja untuk membuat ke NFA tampa ε-move tadak sederhana, perlu melakukan beberapa tahapan yang harus di lewati seperti dengan cara sebagai berikut :

• Buatlah tabel transisi dari NFA dengan ε-move semula

δ	a	b
qo	Ø	Ø
q1	q2	q3
q2	Ø	Ø
q3	Ø	Ø

• Tentukan ε-closure untuk setiap state-state

ε_cl(qo) = {qoq1}

ε_cl(q1) = {q,}

ε_cl(q2) = {q2}

ε_cl(q3) = {q3}

• Kemudian, carilah setiap fungsi transisi hasil perubahan dari NFA ε-move ke NFA tamapa ε-move (kita sebut saja dengan δ') dimana δ'  didapat dengan rumus : 

1. δ'(state,input) = ε-closure (δ (ε-closure (state),input))

δ'(q0, a)  = ε_closure( δ (ε_closure(q0), a))

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

= ε_closure(q2)

= {q2}

 2.  δ'(q0, b) =  ε _closure( δ (ε _closure(qo), b))

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

    = ε _closure(q3)

    = {q3}

  3. δ'(q1, a)   = ε _closure( δ (e.closure(qo), a))

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

    = ε _closure(q2)

    = {q2} 

 4. δ'(q1, b)  =  ε _closure{ δ (ε.closure(q1), b))

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

    = ε _closure(q3)

    = {q3} 

 5. δ'(q2, a)  =  ε _closure( 5 (ε_closure(q2), a))

    = ε _closure( 8 ({q2}, a))

    = ε _closure(0)

    = Ø

 6. δ'(q2, b) = ε closure( 8 (ε_closure(q2), b))

    = ε _closure( 8 ({q2}, b))

    = e_closure(0)

    = Ø

  7. δ'(q3, a) =      e_closure( 8 (e_closure{q3), a))

    = e_closure( 8 ({q3}, a))

    = e_closure(0)

    = Ø

8. δ'(q3, b) =      e_closure( δ (e_closure(q3), b))

    = e_closure( δ ({q3}, b))

    = e_closure(0)

    = Ø 

•  Berdasarkan hasil diatas, kita dapat membuat tabel transisi diagram transisi dari NFA tampa ε_move yang ekuivaen dengan NFA dengan ε_move tersebut

δ'	a	b
qo	q2	q3
q1	q2	q3
q2	Ø	Ø
q3	Ø	Ø

Akhirnya kita tentuka himpunan state akhir untuk NFA tampa ε_move ini. Himpunan state akhit semula (q3). Karena tidak ada state lain yang ε_closure memuat q3 maa himpnan state akhir sekarang tetap q3.

Dapat kita lihat NFA tampa ε_move-nya sebagai berikut :