Teori Bahasa dan Otomata 04 - epsilon NFA

Teori Bahasa dan Otomata

1. TBO NFA dengan Epsilon-Move ( ε NFA)

2. NFA dengan Epsilon-Move NFA dengan ε -Transition NFA dengan ε -Move NFA ε -Move NFA- ε ε NFA

3. Definisi Pada mesin NFA dimungkinkan untuk berpindah kedudukan ( state ) secara seketika ( spontaneously ), dengan kata lain tanpa menerima simbol masukan ( input ) Mekanisme ini membuat suatu mesin NFA bisa berada dalam beberapa state sekaligus Untuk itu dibuatlah Untai-Kosong untuk menggantikan nilai masukan Untai-Kosong itu disimbolkan dengan ε ([ epsilon ]: empty )

4. Ekuivalensi NFA- ε dan NFA Terdapat NFA-ε (Mn 1 ) & NFA (Mn 2 ), jika L (Mn 1 ) = L (Mn 2 ), maka Mn 1 = Mn 2 . Misal: (Mn 1 ) (Mn 2 )

5. Epsilon Closure ( ε -clo) Himpunan state yang dapat dicapai dari suatu state tanpa menerima masukan Setiap state memiliki ε -closure yang menuju ke state itu sendiri.

6. Contoh: ε -closure untuk NFA tersebut: ε -closure(A) = { .... , …. } ε -closure(B) = { .... } ε -closure(C) = { ...., ...., …. }

7. LANGKAH-LANGKAH Mengubah NFA- ε menjadi NFA 1. Buat tabel transisi ε NFA 2. Tentukan ε -closure untuk setiap state 3. Carilah setiap fungsi transisi hasil perubahan dari ε NFA ke NFA ( δ ’) δ’(state,input) = ε-closure( δ(ε-closure(state), input) ) 4. Buat tabel transisi NFA berdasarkan hasil langkah 3 5. Tentukan state akhirnya F’ = F ∪ { Q | (ε-closure( Q ) ∩ F) ≠∅} 6. Buat diagram dari tabel transisi hasil dari langkah 4

8. Contoh Soal: Penyelesaian

9. Latihan 1

10. Latihan 2