Materi 5

 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 dari state q0 tanpa membaca input. Pada suatu state yang tidak memiliki E-Move,  maka E-Closure nya adalah state itu sendiri.

Contoh :

Dari gambar disamping e closure :

1. q0 = {q0,q1}

2. q1 = {q1}

3. q2 = {q2}

4. q3 = {q3}

Ekivalensi NFA dengan E-Move ke NFA tanpa E-Move

langkah-langkahnya adalah sebagai berikut :

1. Buat tabel transisi NFA dengan E-Move

2. Tentukan E-Closure NFA dengan E-Move

3. Tentukan E-Closure NFA dengan E-Move

    δ’ (state,input)= ε-closure(δ(ε-closure(state),input))

4. Buat tabel transisi NFA tanpa E-Move

5. Tentukan state akhir NFA tanpa E-Move

Contoh Soal :

1. Tabel transisi NFA dengan E-Move

2. E-Closure NFA dengan E-Move 

E-Closure(q0) = {q0,q1}

E-Closure(q1) = {q1}

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

3. E-Closure NFA tanpa E-Move

    𝞭'(q0,a) = E-Closure(𝞭(E-Closure(q0),a)

                    = E-Closure(𝞭 ({q0,q1},a))

                    = E-Closure {q0}

                    ={q0,q1}

    𝞭'(q0,a) = E-Closure(𝞭(E-Closure(q0),b)

                    = E-Closure(𝞭 ({q0,q1},b))

                    = E-Closure {q2}

                    ={q0,q1,q2}

    𝞭'(q1,a) = E-Closure(𝞭(E-Closure(q1),a)

                    = E-Closure(𝞭 ({q1},a))

                    = E-Closure {}

                    ={}

    𝞭'(q1,b) = E-Closure(𝞭(E-Closure(q1),b)

                    = E-Closure(𝞭 ({q1},b))

                    = E-Closure {q2}

                    ={q0,q1,q2}

    𝞭'(q2,a) = E-Closure(𝞭(E-Closure(q2),a)

                    = E-Closure(𝞭 ({q0,q1,q2},a))

                    = E-Closure {q0}

                    ={q0,q1}

    𝞭'(q2,b) = E-Closure(𝞭(E-Closure(q2),b)

                    = E-Closure(𝞭 ({q0,q1,q2},b))

                    = E-Closure {q2}

                    ={q0,q1,q2}

4. Tabel transisi NFA tanpa E-Move

5. State akhir NFA tanpa E-Move

State akhir NFA dengan E-Move = q0

E-Closure yang mengandung q0 = E-Closure {q2}

State akhir NFA tanpa E-Move ={q0,q2}