NonDeterministic Finite Automata. B.Very Christioko, S.Kom

NonDeterministic Finite Automata

© B.Very Christioko, S.Kom

Perbedaan DFA dan NFA • DFA (Deterministic Finite Automata) FA di dalam menerima input mempunyai tepat satu busur keluar.

• NFA (Non Deterministic Finite Automata) FA di dalam menerima input mempuyai lebih dari satu busur keluar atau tidak punya busur keluar.


Ekuivalensi antar FA • Terdapat dua mesin FA yaitu M1 dan M2. Dan masingmasing menerima bahasa L(M1) dan L(M2). • Kedua mesin tersebut disebut ekuivalen jika menerima bahasa yang sama yaitu : L(M1) = L(M2)


Definisi Formal NFA • NFA dinyatakan oleh 5 tuple M=(Q , Σ , δ , q0 , F ) ▫ Q = himpunan state ▫ Σ = himpunan simbol input ▫ δ = fungsi transisi ▫ q0 = state awal / initial state ▫ F = state akhir © B.Very Christioko, S.Kom

contoh • G = ({q0 , q1 , q2 , q3, q4 }, {0,1}, δ , q0 , { q2 , q4}}


String diterima NFA bila terdapat suatu urutan transisi berdasar input, dari state awal ke state akhir harus mencoba semua kemungkinan. © B.Very Christioko, S.Kom

Contoh : • string 01001


• Sebuah NFA menerima string, jika: Komputasi pada NFA menerima string. Komputasi adalah :Seluruh inputan dimasukkan dan automata dimulai dari state awal menuju ke state akhir • Sebuah NFA Menolak string, jika: Tidak ada komputasi pada NFA yang menerima string. Untuk setiap komputasi: seluruh inputan selesai dimasukkan dan automata tidak sampai pada State akhir. Atau.. • Inputan belum selesai dimasukkan dan tidak terjadi transisi


Contoh Kasus • Slide Sri Handayaningsih, S.T., M.T. Deterministic Finite Automata (DFA) & NonDeterministic Automata (NFA) (klik disini)


Reduksi Jumlah State pada FSA • Dalam melakukan reduksi jumlah state pada FSA, dikenal dengan istilah: a. Distinguishable (dapat dibedakan) Ciri: - Masing-masing dari kedua state adalah pasangan antara state bukan Final dan state Final. a. Indistinguishable (tidak dapat dibedakan) Ciri: - Kedua state adalah merupakan state bukan final. - Kedua state adalah merupakan state Final © B.Very Christioko, S.Kom

Reduksi Jumlah State pada FSA • Dua buah state dari FSA disebut indistinguishable (tidak dapat dibedakan) apabila :

▫ δ(q,w)∈F sedangkan δ(p,w) ∈ F dan ▫ δ(q,w) ∉F sedangkan δ(p,w) ∉ F untuk semua w ∈ Σ*

• Dua buah state dari FSA disebut distinguishable (dapat dibedakan) bila :

▫ δ(q,w)∈F sedangkan δ(p,w)∉F

untuk semua w ∈ Σ*


Reduksi Jumlah State pada FSA • Oleh karena itu, pasangan dua buah state hanya memiliki salah satu kemungkinan dari indistinguishable dan distinguishable, tidak kedua-duanya. Jika p dan q indistinguishable, dan jika q dan r juga indistinguishable, maka p dan r juga indistinguishable, sehingga dapat kita katakan bahwa ketiga state tersebut indistinguishable


Langkah mereduksi state TAHAP 1: 1. Hapus semua state yang tak dapat dicapai dari state awal, dengan jalan mana pun. 2. Catat semua pasangan state (p,q) yang distinguishable, yaitu {(p,q) | p ∈ F ∧ q ∉ F} 3. Untuk setiap pasangan (p,q) sisanya, untuk setiap a∈ Σ, tentukan δ(p,a) dan δ(q,a) Contoh


TAHAP 1 1. Hapus state yang tidak tercapai -> tidak ada 2. Pasangan distinguishable (q0,q4), (q1,q4), (q2,q4), (q3,q4). 3. Pasangan sisanya (q0,q1), (q0,q2), (q0,q3), (q1,q2) (q1,q3) (q2,q3)


Langkah mereduksi state TAHAP 2: 4. Tentukan pasangan status indistinguishable. 5. Gabungkan setiap group indistinguishable state ke dalam satu state dengan relasi pembentukan group secara berantai : Jika p dan q indistingishable dan jika q dan r indistinguishable maka p dan r indistinguishable, dan p,q serta r indistinguishable semua berada dalam satu group. 6. sesuaikan transisi dari dan ke state-state gabungan.


Tahap 2 Contoh: 1. pasangan status indistinguishable (q1,q2), (q1,q3) dan (q2,q3). 2. q1,q2,q3 ketiganya dapat digabung dalam satu state q123 3. Menyesuaikan transisi, sehingga DFA menjadi


Latihan: • Buku “Teori Bahasa dan Otomata” Firrar Utdirartatmo, Bab 2 halaman 33.


NonDeterministic Finite Automata. B.Very Christioko, S.Kom

Recommend Documents