Materi 6

Non-Deterministic Finite Automata (NFA) dengan e-move

E-Move Berada Pada Transisi State

• Sebuah transisi mempunyai input / output / E-Move.
• Suatu F-Move untuk state q1 ke g2 yang tehubung dapat berpindah tapa menghasilkan inputan apapun pada transisi nya.

Contoh:

Tanpa membaca input :

• gO dapat berpindah ke g1
• q1 dapat berpindah ke q2
• q4 dapat berpindah ke q1

E-Closure ?

E-Closure adalah himpunan state yang dapat di capai dari suatu state tanpa membaca input.

E-Closure (q0) = himpunan state yang dapat dicapai ari stste q0 tanpa membaca input

Pada suatu state yang tidak memiliki E-Move, maka E-Closure nya adalah state itu sendiri

• E-Closure (go) = (q0,q1,q2)
• E-Closure (q1) = (q1,q2)
• E-Closure (q2) = {q2)
• E-Closure (q3) = (q3)
• E-Closure (94) = (q4,q1,q2)

Merubah NFA dengan E-Move ke NFA tapa E-Move

Contoh:

1. Buat table Transisi NFA E-Move dari diagram

NFA semula

2. Cari E-Closure untuk setiap NFA

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

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

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

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

3. Cari setiap tumpsi transisi hasil perubahan dati NI A ke E-Move ke NIA lanpa E Move, dengan rumus

δ(q_0,a) = E-closure (δ(E-closure (q₀),a))

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

              = E-closure (q₂)

              = {q₂}

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

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

              = ε-closure (q₃)

              = {q₃}

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

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

              = ε-closure (q₂)

              = {q₂}

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

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

              = ε-closure (q₃)

              = {q₃}

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

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

              = ε-closure (∅)

              = ∅

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

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

              = ε-closure (∅)

              = ∅

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

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

              = ε-closure (∅)

              = ∅

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

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

              = ε-closure (∅)

              = ∅

3. Bual Tabel Transist baru NFA tanpa E-Move

S. Gambar Diagram Transisi baru NFA tanpa E-Move