NFA (Nondeterministic Finite Automata) Dengan E-Move

Proses Perpindahan State Tanpa Membawa Nilai Input Apapun (empty).

• NFA Dengan E-Move

          NFA dengan E-Move (transisi E-Move), diperbolehkan merubah state tanpa membaca input. Disebut dengan E-Move karena tidak bergantung pada 1 input saat melakukan transisi (perpindahan).

• E-Move Berada Pada Transisi State

        Sebuah transisi mempunyai nilai/output/E-Move. Suatu E-Move untuk state q1 ke q2 yang terhubung dapat berpindah tanpa menghasilkan inputan apapun pada transisinya.

Contoh :

Tanpa membaca inputan :

• q0 dapat berpindah ke q1
• q1 dapat berpindah ke q2
• q4 dapat berpindah ke q1

E-Clouser 

• E-Closure adalah himpunan state yang dapat di capai dari suatu state tanpa membaca input.
• E-Closure (q0) = himpunan state yang dapat dicapai dari state q0 tanpa membaca input.
• Pada suatu state yang tidakk memiliki E-Move maka E-Closure nya adalah state itu sendiri.

Contoh :

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

Proses Merubah NFA dengan E-Move Ke NFA tanpa E-Move

Contoh diagram transisi :

1. Buat tabel transisi NFA E-Move dari diagram NFA semula (gambar diatas)

2. Cari E-Closure untuk setiap FSA

• E-Closure (q0) = {q0, q1}
• E-Closure (q1) = {q1}
• E-Closure (q2) = {q2}
• E-Closure (q3) = {q3}

3. Cari setiap fungsi transisi hasil perubahan dari NFA ke E-Move ke NFA tanpa E-Move

    Dengan Rumus :

δ' (q0,a)       = E-CL (δ' (E-CL (q0),a)

                   = E-CL (δ' (q0,q1),a)

                   = E-CL (q2)

                   = {q2}

δ' (q0,b)      = E-CL (δ' (E-CL (q0),b)

                   = E-CL (δ' (q0, q1),b)

                   = E-CL (q3)

                   = {q3}

δ' (q1,a)       = E-CL (δ' (E-CL (q1),a)

                   = E-CL (δ' (q1),a)

                   = E-CL (q2)

                   = {q2}

δ' (q1,b)      = E-CL (δ' (E-CL (q1),b)

                   = E-CL (δ' (q1),b)

                   = E-CL (q3)

                   = {q3}

δ' (q2,a)       = E-CL (δ' (E-CL (q2),a)

                   = E-CL (δ' (q2),a)

                   = E-CL (Ø)

                   = Ø

δ' (q2,b)      = E-CL (δ' (E-CL (q2),b)

                   = E-CL (δ' (q2),b)

                   = E-CL (Ø)

                   = Ø

δ' (q3,a)       = E-CL (δ' (E-CL (q3),a)

                   = E-CL (δ' (q3),a)

                   = E-CL (Ø)

                   = Ø

δ' (q0,b)      = E-CL (δ' (E-CL (q3),b)

                   = E-CL (δ' (q3),b)

                   = E-CL (Ø)

                   = Ø

4. Buat tabel transisi NFA tanpa E-Move

5. Buat diagram NFA tanpa E-Move (tabel tansisi diatas)

Contoh Lainnya :