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 :
