Otomata & Teori Bahasa

MENGUBAH NFA DENGAN Ɛ-MOVE KE NFA TANPA Ɛ-MOVE

NFA dengan Ɛ-move ( NFA Ɛ-move ) Disini kita mempunyai jenis otomata baru yang disebut NFA dengan  Ɛ-move(Ɛ disini bisa dianggap sebagai empty). Pada NFA dengan Ɛ-move (transisi Ɛ), diperbolehkan merubah state tanpa membaca input. Disebut dengan transisi Ɛ karena tidak bergantung pada suatu input ketika melakukan transisi.

Contoh:

Mesin NFA dengan  Ɛ-move

Ɛ-closure untuk NFA Ɛ-move.

Sekarang kita akan menambah suatu pengertian baru yang disebut Ɛ-closure. Ɛ-closure adalah himpunan state-state yang dapat dicapai dari suatu state tanpa membaca input. Misalkan saja Ɛ-closure(q0) = himpunan-himpunan state-state yang dapat dicapai dari state q0 tanpa membaca input. Maka dengan melihat gambar Ɛ-closure (q0)= {q0,q1,q2,} artinya dari state q0 tanpa membaca input dapat mencapai state q0, q1, dan q2. Ɛ-closure untuk state lainnya bisa dilihat sebagai berikut:

Ɛ-closure (q1) = {q1,q2}
Ɛ-closure (q2) = {q2}
Ɛ-closure (q3) = {q3}
Ɛ-closure (q4) = {q1,q2,q4}

Ekivalensi NFA Ɛ-move ke NFA tanpa Ɛ-move

Dari sebuah NFA dengan Ɛ-move dapat kita peroleh NFA tanpa Ɛ-move yang ekivalen.
contoh NFA dengan Ɛ-move

NFA Ɛ-move   

Cara mengubah NFA dengan Ɛ-move ke NFA tanpa Ɛ-move
langkah - langkahnya

1. Buat table transisi NFA dengan Ɛ-move semula
2. Tentukan Ɛ-closure untuk setiap state
3. Carilah setiap fungsi transisi hasil perubahan dari NFA Ɛ-move ke NFA tanpa Ɛ-move (kita sebut saja      
     sebagai δ’) dimana δ’ didapatkan dengan rumus: δ’(state, input) = Ɛ_closure (δ(Ɛ_closure(state, input))
4. Berdasarkan hasil no (3), kita bisa membuat table transisi dan diagram transisi dari tanpa Ɛ-move yang
     ekivalen dengan NFA Ɛ-move tersebut.
5. Jangan lupa menentukan state-state akhir untuk NFA 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 U {q}(Ɛ-closure (q) n F) tidak sama dengan ᴓ}
Misal: bila semula F= {q0, q3}, Ɛ_closure {q1}, = {q0, q2}, maka F’={q0, q1, q3}.

dari gambar di atas dapat di kerjakan sebagai berikut
1. tabel transisi dari gambar di atas

Dari NFA Ɛ-move pada gambar kita bisa tentukan Ɛ-closure untuk setiap state (Ɛ-closure bisa juga kita singkat sebagai Ɛ-cl):
Ɛ_cl (q0) = {q0,q1}
Ɛ_cl (q1) = {q1}
Ɛ_cl (q2) = {q2}
Ɛ_cl (q3) = {q3}
2. Kemudian kita cari  δ’ dengan memanfaatkan table 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 (q3)
             = {q3}

δ’(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 (ᴓ)
             = ᴓ


Bisa kita lihat table transisi untuk NFA tanpa Ɛ-move dari hasil diatas:

NFA tanpa Ɛ-move