NFA Empty - move

TEORI BAHASA DAN OTOMATA

NFA (Nondeterministic Finite Automata)  dengan ε-move

Disini kita mempunyai jenis otomata baru yang disebut Nondeterministic Finite Automata dengan ε-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 :

ε-closure

ε-closure adalah himpunan state-state yang dapat dicapai dari suatu state tanpa membaca input.

Contoh dari gambar di atas cari ε-closure :

Jawab :

ε-closure(q0)={q0,q1}

ε-closure(q1)={q1}

ε-closure(q2)={q2}

ε-closure(q3)={q3}

Contoh dari gambar di atas cari ε-closure :

Jawab :

ε-closure(q0)={q0,q1,q3}

ε-closure(q1)={q1,q3}

ε-closure(q2)={q2,q4}

ε-closure(q3)={q3}

ε-closure(q4)={q4}

Keterangan : 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. Langkahnya adalah sebagai berikut :

1.   Buat tabel transisi NFA dengan ε-move

2.   Tentukan ε-closure NFA dengan ε-move

3.   Tentukan ε-closure NFA tanpa ε-move dengan rumus

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

4.   Buat tabel transisi NFA tanpa ε-move

5.   Tentukan state akhir NFA tanpa ε-move

(State akhir semula  ditambah dengan state yang ε-closure nya menuju ke salah satu dari state akhir semula)

Contoh Soal

Diketahui :

Ditanya :

1.   Buat tabel transisi NFA dengan ε-move

2.   Tentukan ε-closure NFA dengan ε-move

3.   Tentukan ε-closure NFA tanpa ε-move

4.   Buat tabel transisi NFA tanpa ε-move

5.   Tentukan state akhir NFA tanpa ε-move

Jawab :

5.   State akhir NFA tanpa ε-move

State akhir NFA dengan ε-move = q0

ε-closure yang mengandung q0= ε-closure {q2}

State akhir NFA tanpa ε-move ={q0,q2}

SUMBER :https://aprilhardi.wordpress.com/