BAB I
PENDAHULUAN
1.1
Latar Belakang
Di sini kita mempunyai jenis otomata baru yang disebut Non- deterministic Finite Automata dengan ɛ-move.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.ε-closureadalahhimpunan state-state yang dapatdicapaidarisuatu state tanpamembaca input
1.2
Rumusan Masalah
•
Apa itu Non-Deterministic Finite Automata ?
•
Bagaimana NFA dengan ɛ-Move !
•
Apa itu ɛ-Clouser ?
•
Mengerti bagaimana tahapan dalam proses eqkuivalensi pada mesin
1.3
Tujuan Penulisan
•
Mengetahui apa itu Non-Deterministic Finite Automata
•
Mengetahui apa itu ɛ-cluoser
•
Mengetahui ekivalensi NFA dengan ɛ-move ke NFA tanpa ɛ-move
BAB II
PENJELASAN
NON-DETERMINISTIC FINITE AUTOMATA DENGAN ɛ-MOVE
2.1
NON-DETERMINISTIC FINITE AUTOMATA DENGAN ɛ-MOVE
Di sini kita mempunyai jenis otomata baru yang disebut Non- deterministic Finite Automata dengan ɛ-move (ɛ di sini 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. Contohnya bisa dilihat Pada gambar 1.
Penjelasan gambar 1
- dari q0 tanpa membaca input dapat berpindah ke q1
- dari q1 tanpa membaca input dapat berpindah ke q2
- dari q4 tanpa membaca input dapat berpindah ke q1
Salah satu kegunaan dari transisi ε ini adalah memudahkan kita untuk mengkombinasikan finite state automata.
2.2
ε-CLOSURE UNTUK SUATU NON-DETERMINISTIC FINITE AUIOMATA DENGAN ε-MOVE
Sekarang kita akan menambah suatu pengertian baru sebut ε-closure. ε-closure adalah himpunan state-state yang dapat dicapai dari suatu state tanpa membaca input. Misalkan saja ε-closure(q0) himpunan himpunan state-state yang dapatdicapai dan state q0 tanpa membaca input. Maka dengan melihat gambar 1.
ε -closure(q0) {q0,q1,q2}, artinya dari state q0 tanpa membaca input dapat mencapai state q0, q1, dan q2 ε -closure untuk state lainnya bias dilihat sebagai berikut.
ε -closure(q1) = (q1, q2)
ε -closure(q2) = (q2)
ε -closure(q4) = (q1, q2, q4)
Contoh lain kita lihat pada gambar2.
 |
| Mesin NFA dengan ε -move |
Gambar 2, Mesin NFA dengan ε -move
Dari gambar 2, kitaketahui ε -closure untuksetiap state adalahsebagaiberikut.
ε -closure(q0) = {q0, 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 ε, maka ε - closure-nyaadalah state itu sendiri.
2.3 EKUIVALENSI NON-DETERMINISTIC FINITE AUTOMATA DENGAN ε -MOVE KE NON DETERMINISTIC FINITE AUTOMATA TANPA ε -MOVE
Dari sebuah Non-deterministic Finite Automata dengan ε -move dapat kita peroleh Non-deterministic Finite Automata tanpaε -move yang ekuivalen. (Dalam makalah ini sebutan NFA saja mengacu kepada NFA tanpa t-move).Contohnya, bila kita punya NFA ε -move, seperti pada gambar 3.
 |
| Gambar 3. NFA ε -move |
Gambar 4.4 adalah NFA tanpa ε -move yang ekuivalendengan NFA ε -move pada gambar3.
 |
| Gambar 4. NFA tanpa ε -move ekuivalen gambar 3. |
Perhatikan bahwa Non-deterministic Finite Automata ε -move semula menerima bahasa yang memuat string ‘b’, selanjutnya kita lihat bahwa Non-deterministic Finite Automata tanpa ε -move pada gambar4. Juga mampu menerima bahasa yang memuat string 'b'. Maka, kita dapat menyatakan bahwa kedua mesin tersebut ekuivalen, karena mampu menerima bahasa yang sama.
Tentu saja bila gambarnya tidak sesederhana itu, kita perlu melakukan beberapa tahapan untuk mendapatkan perubahan dari Non deterministic Finite Automata e-move ke Non-deterministic Finite Automata tanpa ε-move.
Secara umum caranya adalah sebagai berikut :
1. Buat tabel transisi Non-deterministic Finite Automata ε -move semula
2. Tentukan ε -closure untuksetiap state
3. Carilah setiap fungsi transisi hasil perubahandari Non-determinenistic Finite Automata ε -move ke Non-deterministic Finite Automata tanpa ε -move (kita sebut saja sebagai δ) di mana δ didapatkan dengan rumus:
δ (state, input) input) = ε_closure (δ (ε_closure(state), input )
4 .Berdasarkan hasil nomor (3) kita bisa membuat tabel transisi dan diagram transisi dari non deterministic Finite Automata tanpa ε-move yang ekuivalen dengan Non-deterministtc Finite Automata ε -move tersebut.
5. Jangan lupa menentukan state-state akhir untuk Non-deterministic Finite Automata tanpa ε -move tersebut, yaitu state-state akhir semula ditambah dengan state-state yang ε _closure-nya menuju ke salah satu dari state akhir semula.
Dalam bahasa formalnya:
F'=F ᴜ (q | (ε -closure(q) ∩ F) ≠ Ø )
Misalnya: bila semula F (q0,q3), ε _closure (q1) = (q0, q2) maka Tabel transisi dari NFA e-move pada gambar3.
δ
a
B
q0
Ø
Ø
q1
q2
q3
q2
Ø
Ø
q3
Ø
Ø
Dari Non-deterministic Finite Automata ε -move pada gambar 3.kita bias tentukan ε -closure untuk setiap state (ε -closure bias kita juga singkat sebagai ε -cl):
ε _cl(q0) = {qo,q1}
ε _cl(q1) = { q1}
ε _cl(q2) ={ q2}
ε _cl(q3) ={ q3}
Kemudian kita cari δ dengan memanfaatkan tabel transisi dan ε -closure yang kita peroleh sebelumnya, sebagai berikut.
δ’ (q0,a)
= ε_closure(δ (ε_closure(q0), a) )
= ε_closure(δ ({q0, q1}, a) )
= ε _closure (q2)
= {q2}
δ’ (q0,b)
= ε_closure(δ (ε_closure(q0), b) )
= ε_closure(δ ({q0, q1}, b) )
= ε _closure (q3)
= {q3}
δ’ (q1,a)
= ε_closure(δ (ε_closure(q1), a) )
= ε_closure(δ ({q1}, a) )
= ε _closure (q2)
= {q2}
δ’ (q1,b)
= ε_closure(δ (ε_closure(q1), b) )
= ε_closure(δ ({q1}, b) )
= ε _closure (q3)
= {q3}
δ’ (q2,a)
= ε_closure(δ (ε_closure(q2), a) )
= ε_closure(δ ({q2}, a) )
= ε _closure (Ø)
= { Ø }
δ’ (q2,b)
= ε_closure(δ (ε_closure(q2), b) )
= ε_closure(δ ({q2}, b) )
= ε _closure (Ø)
= { Ø }
δ’ (q3,a)
= ε_closure(δ (ε_closure(q3), a) )
= ε_closure(δ ({q3}, a) )
= ε _closure (Ø)
= { Ø }
δ’ (q3,b)
= ε_closure(δ (ε_closure(q3), b) )
= ε_closure(δ ({q3}, b) )
= ε _closure (Ø)
= { Ø }
Kita bias melihat tabel transisi untuk NFA tanpa ε -move dan hasil di atas. Akhirnya kita tentukan himpunan state akhir untuk Non _ deterministic Finite Automatatanpa ε -move ini. Himpunan state akhir semula adalah (q3). Karena tidak ada state lain yang ε -closure-nya memuat q3, maka himpunan state akhir sekarang tetap {q3}
Sekarang Anda dapat menggambarkan Non-deterministic Finite Automatatanpa ε-move. Periksalah hasilnya dengan gambar 4.
Catatan!
Perhatikan bahwa karena di sini mesin Non-deterministic Finite Automata maka state Ø tidak, perlu kita munculkan dalam diagram transisi. Kita coba dengan contoh lain, perhatikan gambar 5.
Gambar 5 NFA ε-move
Lihat tabel transisi berikut untuk NFA ε -move pada gambar5.
δ
a
B
q0
{q0}
Ø
q1
Ø
{q2}
q2
Ø
{q2}
Kita tentukan ε -cl untuk setiap state dari gambar 5:
ε –cl(q0)
= {q0, q1}
ε –cl(q1)
= {q1}
ε -cl(q2)
= {q0, q1, q2}
Selanjutnya kita tentukan δ’ sebagai berikut.
δ’ (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 }
Berdasarkan hasil di atas dapat kita buat tabel transisi untukNFA tanpaε-move sebagai
berikut.
δ'
A
B
q0
{q0, q1}
{ q0,q1, q2 }
q1
Ø
{ q0,q1, q2 }
q2
{q0, q1}
{ q0,q1, q2 }
Akhirnya kita tentukan himpunan state akhir untuk Non-deterministic Finite Automata tanpa ε-move ini. Himpunan state akhir semula adalah (q0). Kita lihatε -c1(q2) { q0,q1, q2 }, sehingga himpunan state sekarang{q0, q2}.
Sekarang kita dapat membuat diagram transisi untuk Non-deter ministic Finite Automata tanpa ε-move, yang dapat dilihat pada gambar 6.
Gambar 6. NFA tanpa ε-move yang ekuivalen dengan gambar 5.
Contoh lain, perhatikan Non-deterministic Finite Automata ε-move pada gambar 7. Non deterministic Finite Automatatanpa ε-move yang ekuivalen dengan gambar7. Bisa kita lihat pada gambar 8.
Gambar 7 NFA ε –move
Gambar 8 NFA tanpa ε -move
Misalkan, diketahui bahwaNon-deterministic Finite Automata, ε -move semula (gambar 7) menerima bahasa dengan ekspresi regu. Lar= 0* , maka dapat kita lihat bahwa Non-deterministic Finite Automata tanpa ε-move ekuivalennya juga menerima bahasa yang sama.
Perhatikan bahwa dalam menentukan state-state akhir, kita juga memperhitungkan transisi-transisi ε sebelum state akhir semula.
2.4 PENGGABUNGAN DAN KONKATENASI FINITE STATE AUTOMATA
Pada dua mesin finite automata kita dapat melakukan penggabungan, disebut union, serta konkatenasi.Misalkan, kita mempunyai dua buah mesin NFA, M1 pada gambar 9, dan M2 pada gambar 10.
Gambar 9. Mesin M1
Gambar 10 Mesin M2
Bila diketahui L (M1) adalah bahasa yang diterima oleh M1, dan L(M2) adalah bahasa yang diterima oleh M2. Dilakukan operasi union berikut. L(M3) = L(M1) L(M2)(atau dengan notasi lain: L(M3) = L(M1)+L(M2)). Kita bisa membuat mesin M3 yang menerima bahasa L(M3) denagn cara sebagai berikut.
•
Tambahkan state awal untuk M3, hubungkan dengan state awal M1 dan state awal M2 menggunakan transisi ɛ.
•
Tambahkan state akhir untuk M3, hubungkan dengan state-state akhir M1, dan state-state akhir M2 menggunakan transisi ɛ.
Kita lihat hasil operasi union ini pada gambar 11. qs dan qf adalah state awal dan state final mesin baru kita.
Gambar 11. Mesin M3
Ditentukan L(M4) = L(M1) L(M2). Kita bisa membuat mesin M4 yang menerima bahasa L(M4) dengan cara sebagai berikut
•
State awal M1 menjadi state awal M4.
•
State -state akhir M2 menjadi menjadi state akhir M4.
•
Hubungkan state-state akhir M1 dengan state awal M2 menggunakan transisi ɛ.
Kita dapat melihat hasil operasi konkatenasi ini pada gambar 12.
Gambar MEsin M4
BAB III
PENUTUP
3.1 kesimpulan
NON-DETERMINISTIC FINITE AUTOMATA DENGAN ɛ-MOVE jenis otomata baru yang disebut Non- deterministic Finite Automata dengan ɛ-move (ɛ di sini 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 AUIOMATA DENGAN ε-MOVE ε-closure adalah himpunan state-state yang dapat dicapai dari suatu state tanpa membaca input
EKUIVALENSI NON-DETERMINISTIC FINITE AUTOMATA DENGAN ε -MOVE KE NON DETERMINISTIC FINITE AUTOMATA TANPA ε -MOVE kita dapat menyatakan bahwa kedua mesin tersebut ekuivalen, jika mesin tersebut mampu menerima bahasa yang sama. Dengan kita perlu melakukan beberapa tahapan untuk mendapatkan perubahan dari Non deterministic Finite Automata e-move ke Non-deterministic Finite Automata tanpa ε-move.
PENGGABUNGAN DAN KONKATENASI FINITE STATE AUTOMATA Pada dua mesin finite automata kita dapat melakukan penggabungan, disebut union, serta konkatenasi.
DAFTAR PUSTAKA
Utdirartatmo, Firrar. Teori Bahasa Dan Otomata edisi kedua: Graha Ilmu.
Rajeev, Jeffrey dan E. Hopcroft John. 2007. Teori Bahasa Dan Otomata: Penerbit Andi.
