NON DETERMINISTIC FINITE AUTOMATA(NFA) DENGAN ɛ-MOVE
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
ε-CLOSURE UNTUK SUATU NON-DETERMINISTIC FINITE AUIOMATA DENGAN ε-MOVE
ε-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)
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
Contoh Gambar 3. NFA ε -move
Contoh Gambar 4. NFA tanpa ε -move ekuivalen gambar 3.
Tahapan untuk mendapatkan perubahan dari Non deterministic Finite Automata e-move ke Non-deterministic Finite Automata tanpa ε-move. Secara umum caranya adalah sebagai berikut :
- Buat tabel transisi Non-deterministic Finite Automata ε -move semula
- Tentukan ε -closure untuksetiap state
- 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) ≠ Ø ) 2.4 PENGGABUNGAN DAN KONKATENASI FINITE STATE AUTOMATA
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 ɛ.
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
Lanjut memenetukan M4
Ditentukan L(M4) = L(M1) L(M2).
Caranya :
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 ɛ.
Dapatkan Slide PPT (power pointn) Di Dropbox
