Sergius' Business

Kali ini saya akan mengulas tentang Ekuivalensi NFA dengan    Ɛ -move ke NFA.Konsepan apa itu NFA,   Ɛ -move,Ekuivalensi NFA dengan    Ɛ -move ada di postingan saya sebelumnya. 1.) Buat    Ɛ-closure-nya ·          Ɛ-closure (q0) = {q0,q1} ·          Ɛ-closure (q1) = {q1} ·          Ɛ-closure (q2) = {q2} ·          Ɛ-closure (q3) = {q3}  2.) Buat Tabel Transisi δ a b q0 θ θ q1 q2 θ q2 θ θ q3 θ θ 3.) Tentukan Perubahan State-nya a)       δ’ (q0,a)= Ɛ-cl ( ( δ-cl ( q0 ), a) ) ) = Ɛ-cl ( ( δ( q0, q1 ), a) ) )   = Ɛ-cl (q2) =q2 δ’ (q0,b)= Ɛ-cl ( ( δ-cl ( q0 ), b) ) ) = Ɛ-cl ( ( δ( q0, q1 ), b) ) )   = Ɛ-cl (q3) =q3 b)       δ’ (q1,a)= Ɛ-cl ( ( δ-cl ( q1 ), a) ) ) = Ɛ-cl ( ( δ( q1 ), a) ) )   = Ɛ-cl (q2) =q2 δ’ (q1,b)= Ɛ-cl ( ( δ-cl ( q1 ), b) ) ) = Ɛ-cl ( ( δ( q1 ), b) ) )   =

Penjelasan: ·          Dari q0 tanpa membaca input dapat berpindah ke q1 ·          Dari q1 tanpa membaca input dapat berpindah ke q2 ·          Dari q4 tanpa membaca input dapat berpindah ke q1 Ɛ-closure adalah himpunan state-state yang dapat dicapai dari suatu state tanpa membaca input.Perhatikan gambar sebelumnya maka Ɛ-closure diperoleh : ·          Ɛ-closure (q0) = {q0,q1,q2} ·          Ɛ-closure (q1) = {q1,q2} ·          Ɛ-closure (q2) = {q2} ·          Ɛ-closure (q3) = {q3} ·          Ɛ-closure (q4) = {q1,q2,q4} Catatan :   Ɛ (dibaca empty (emti)) adalah input yang bernilai kosong/tanpa membaca input. Pada      Ɛ-closure,jika tidak ada input  Ɛ, maka cukup masukkan state yang ingin di-   Ɛ-closure tadi.Misalnya,tidak ada hasil dari      Ɛ-closure (q2),maka masukkan q2 sebagai hasilnya,menjadi      Ɛ-closure(q2)={q2}. Lanjutan dari materi ini adalah  Ekuivalensi NFA dengan Ɛ-move ke NFA

NFA 1.) Buat Tabel Transisi δ 0 1 q0 {q0, q1} q1 q1 θ {q0, q1} 2.) Buat Tupel δ  = {q0 , q1} Ʃ = {0 , 1} s =  q0 f =  q1 3.) Buat DFA Sederhanakan dengan memakai table transisi tadi sebagai panduan dalam membuat diagramnya sehingga akhirnya didapatkan bentuk baru dari diagramnya. Catatan : Diketahui di awal bahwa q1 merupakan final state.Maka dari itu,semua state yang mengandung q1 harus memiliki lingkaran tambahan sebagai tanda final state.Contohnya pada state {q0, q1} yang mengandung unsur q1 sehingga diberi tambahan lingkaran final state.