0

Non-deterministic Finite Automata Dengan ε-Move

Posted by Jujur Sitanggang on 6:26 PM

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 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.

ε-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(q0) = himpunan state-state yang dapat dicapai dari state q0 tanpa membaca input.Maka dengan melihat contoh diatas ε-closure(q0) = { q0, q1, q2}, artinya dari state q0 tanpa membaca input dapat mencapai state q0, q1, q2.
ε-closure(q0) = { q0, q1, q2},
ε-closure(q1) = { q1, q2},
ε-closure(q2) = { q2},
ε-closure(q3) = { q3},
ε-closure(q4) = { q1, q2, q4}
*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(q0) = { q0, q1},
ε-closure(q1) = { q1},
ε-closure(q2) = { q2},
ε-closure(q3) = { q3}
kemudian kita cari d’ dengan memanfaatkan tabel transisi dan ε-closure yang kita peroleh sebelumnya,sebagai berikut:
d(q0,a) = ε-closure (δ(ε-closure (q0),a))
              = ε-closure (δ ({ q0, q1},a))
              = ε-closure (q2)
              = {q2}
d(q0,b) = ε-closure (δ(ε-closure (q0),b))
              = ε-closure (δ({ q0, q1},b))
              = ε-closure (q3)
              = {q3}
d(q1,a) = ε-closure (δ(ε-closure (q1),a))
              = ε-closure (δ({ q1},a))
              = ε-closure (q2)
              = {q2}
d(q1,b) = ε-closure (δ(ε-closure (q1),b))
              = ε-closure (δ({q1},b))
              = ε-closure (q3)
              = {q3}
d(q2,a) = ε-closure (δ(ε-closure (q2),a))
              = ε-closure (δ({q2},a))
              = ε-closure (θ)
              = θ
d(q2,b) = ε-closure (δ(ε-closure (q2),b))
              = ε-closure (δ({q2},b))
              = ε-closure (θ)
              = θ
d(q3,a) = ε-closure (δ(ε-closure (q3),a))
              = ε-closure (δ({ q3},a))
              = ε-closure (θ)
              = θ
d(q3,b) = ε-closure (δ(ε-closure (q3),b))
              = ε-closure (δ({ q3},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}.

 


0 Comments

Copyright Jujur Soaloon Sitangang Lipan All rights reserved. Theme by Sitanggang. | Bloggerized by Soalparna.