Non-deterministic Finite Automata Dengan ε-Move

Non-deterministic Finite Automata (NFA) Dengan ε-Move

note d = teta

Di sini kita mempunyai jenis otomata baru yang disebut Non-deterministic Finite Automata dengan ε-move (ε-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:

·         Dari q₀ tanpa membaca input dapat berpindah ke q₁

·         Dari q₁ tanpa membaca input dapat berpindah ke q₂

·         Dari q₄ tanpa membaca input dapat berpindah ke q₁

Salah satu kegunaan dari transisi ε ini adalah memudahkan kita untuk mengkombinasikan Finite State Automata.

ε-Closure untuk Suatu Non-deterministic Finite Automata (NFA) dengan ε-Move

ε-Closure adalah himpunan state-state yang dapat dicapai dari suatu state tanpa membaca input. Misalkan saja ε-closure(q₀) = himpunan state-state yang dapat dicapai dari state q₀ tanpa membaca input.Maka dengan melihat contoh diatas ε-closure(q₀) = { q_0, q_1, q₂}, artinya dari state q₀ tanpa membaca input dapat mencapai state q_0, q_1, q_2.

ε-closure(q₀) = { q_0, q_1, q₂},

ε-closure(q₁) = { q_1, q₂},

ε-closure(q₂) = { q₂},

ε-closure(q₃) = { q₃},

ε-closure(q₄) = { q_1, q_2, q₄}

*Perhatikan: Pada suatu state yang tidak memiliki transisi ε, maka ε-closure-nya adalah state itu sendiri.

Ekivalensi NFA dengan ε-Move ke NFA tanpa ε-Move  

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

Contoh:

Tabel transisi dari NFA ε-move diatas adalah:

d	a	b
q0	θ	θ
q1	q2	q3
q2	θ	θ
q3	θ	θ

State akhir (F) adalah state q3

ε-closure untuk setiap state nya:

ε-closure(q₀) = { q_0, q₁},

ε-closure(q₁) = { q₁},

ε-closure(q₂) = { q₂},

ε-closure(q₃) = { q₃}

kemudian kita cari d’ dengan memanfaatkan tabel transisi dan ε-closure yang kita peroleh sebelumnya,sebagai berikut:

d’ (q_0,a) = ε-closure (δ(ε-closure (q₀),a))

              = ε-closure (δ ({ q_0, q₁},a))

              = ε-closure (q₂)

              = {q₂}

d’ (q_0,b) = ε-closure (δ(ε-closure (q₀),b))

              = ε-closure (δ({ q_0, q₁},b))

              = ε-closure (q₃)

              = {q₃}

d’ (q_1,a) = ε-closure (δ(ε-closure (q₁),a))

              = ε-closure (δ({ q₁},a))

              = ε-closure (q₂)

              = {q₂}

d’ (q_1,b) = ε-closure (δ(ε-closure (q₁),b))

              = ε-closure (δ({q₁},b))

              = ε-closure (q₃)

              = {q₃}

d’ (q_2,a) = ε-closure (δ(ε-closure (q₂),a))

              = ε-closure (δ({q₂},a))

              = ε-closure (θ)

              = θ

d’ (q_2,b) = ε-closure (δ(ε-closure (q₂),b))

              = ε-closure (δ({q₂},b))

              = ε-closure (θ)

              = θ

d’ (q_3,a) = ε-closure (δ(ε-closure (q₃),a))

              = ε-closure (δ({ q₃},a))

              = ε-closure (θ)

              = θ

d’ (q_3,b) = ε-closure (δ(ε-closure (q₃),b))

              = ε-closure (δ({ q₃},b))

              = ε-closure (θ)

              = θ

Bisa kita lihat tabel transisi untuk NFA tanpa ε-move dari hasil di atas:

d’	a	b
q0	q2	q3
q1	q2	q3
q2	θ	θ
q3	θ	θ

Terakhir kita tentukan state akhir untuk NFA tanpa ε-move ini. Himpunan state akhir semula adalah {q3}.Karena tidak ada state lain yang ε-closurenya memuat q3, maka himpunan state akhir sekarang tetap {q3}.