Ekuivalensi NFA Ke DFA [PDF]

Citation preview

TEORI BAHASA OTOMATA EKUIVALENSI



Disusun Oleh : 1. AYU ANGGRAINI



1410651007



2. HENI NOVIYA ISMA WATI



1410651024



3. NANI DWI INDRI ASTUTI



1410651142



Dosen Pengampu : GINANJAR ABDURRAHMAN, S.Si., M.Pd.



JURUSAN TEKNIK INFORMATIKA FAKULTAS TEKNIK UNIVERSITAS MUHAMMADIYAH JEMBER 2017



Pengertian Ekuivalensi Antar DFA Pada bahasa reguler, kemungkinan ada sejumlah deterministic finite automata yang dapat menerimanya. Perbedaannya hanya terletak pada jumlah state yang dimiliki otomata-otomata yang saling ekuivalensi. Ada dua buah istilah baru yang perlu kita ketahui : 1. Distinguishable yang berarti dapat dibedakan. 2. Indistinguishabe yang berarti tidak dapat dibedakan. Dua deterministic finite automata M1 dan M2 dinyatakan ekuivalensi apabila L(M1) = L(M2).



Ekuivalensi NFA ke DFA Sebuah mesin Non-deterministic Finite Automata dapat dibuat mesin Deterministic Finite Automata yang Ekuivalen. Ekuivalen artinya menerima bahasa yang sama meskipun yang satu adalah Non-deterministic Finite Automata dan yang satunya Deterministic Finite Automata namun keduanya menerima bahasa yang sama. DFA yang ekuivalen dengan NFA Deterministic Finite Automata yang Ekuivalen dengan Non-deterministic Finite Automata.



Pertama buatlah tabel transisi



Kedua kita buat tupel dari tabel tersebut agar lebih detail δ = {q0 , q1} Ʃ = {0 , 1} s = q0 f = q1 Lalu kita mulai membuat DFA nya ,dimulai dari state awal q0 State {q0} bila memperoleh input 0 menjadi state {q0, q1}. State {q0} bila memperoleh input 1 menjadi state {q1}.



Ekivalensi Non-Deterministic Automata (NFA) ke Deterministic Finite Automata (DFA) State {q1} memperoleh input 0 menjadi state ∅ State {q1} bila memperoleh input 1 menjadi state {q0, q1}.



Pada state {q0,q1} awalnya belum mempunyai busur dan pada DFA,sebuah state harus mempunyai busur sebanyak himpunan inputnya, karena itu kita tentukan terlebih dahulu arah busurnya dan busurnya ada 2. δ({q0,q1},0) = {q0,0} ε {q1,0} = {q0,q1} ε Ø = {q0,q1} δ({q0,q1},1) = {q0,1} ε {q1,1} = {q1} ε {q0,q1} = {q0,q1} Jadi arah busur pada state {q0,q1} mengarah ke state itu sendiri. Kemudian khusus pada state himpunan kosong (Ø) hanya menerima inputan dari statenya sendiri,jadi busur pada himpunan kosong mengarah ke state himpunan kosong.



Ekivalensi Non-Deterministic Automata (NFA) ke Deterministic Finite Automata (DFA) Terakhir untuk menentukan final state pada DFA ini adalah dengan melihat NFA yang ekuivalen dengan DFA ini yaitu soal awal, Kita ketahui Bahwa final state adalah q1,jadi pada DFA final statenya adalah semua state yang ada hubungannya dengan q1 yaitu {q0,q1} dan {q1}



Ekivalensi Non-Deterministic Automata (NFA) ke Deterministic Finite Automata (DFA)



Ekuivalensi Antar DFA



 State q5 tidak dapat dicapai dari state awal dengan jalan apapun (useless state). Maka hapus state q5  Catat state-state distinguishable yaitu : q4  F sedang q0, q1, q2, q3 F sehingga pasangan (q0, q4) (q1, q4) (q2, q4) dan (q3, q4) adalah distinguishable.  Pasangan - pasangan state lain yang distinguishable diturunkan berdasarkan pasangan dari langka 2 yaitu :  Untuk pasangan (q0, q1) δ(q0, 0) = q1 dan δ(q1, 0) = q2  Belum teridentifikasi δ(q0, 1) = q3 dan δ(q1, 1) = q4 (q3, q4) distinguishable maka (q0, q1) adalah distinguishable.  Untuk pasangan (q0, q2) δ(q0, 0) = q1 dan δ(q2, 0) = q1 Belum teridentifikasi δ(q0, 1) = q3 dan distinguishable.



δ(q2, 1) = q4 (q3, q4) distinguishable maka (q0, q2) adalah



 Setelah diperiksa semua pasangan state maka terdapat state-state yang distinguishable : (q0,q1), (q0,q2), (q0,q3), (q0,q4), (q1,q4), (q2,q4), (q3,q4) Karena berdasarkan relasi - relasi yang ada,tidak dapat dibuktikan (q1,q2),(q1,q3) dan (q2,q3) distinguishable, sehingga disimpulkan pasangan - pasangan state tersebut indistinguishable.  Karena q1 indistinguishable dengan q2, q2 indinguishable denganq3, maka dapat disimpulkan q1,q2,q3 saling indistinguishable dan dapat dijadikan satu state.



 Berdasarkan hasil diatas maka hasil dari DFA yang direduksi menjadi :