Institute Teknologi PLN Jakarta
Dosen : Dine Tiara Kusuma S.T., M.Kom
EKUIVALENSI NFA KE
DFA
Ekuivalensi Non-Deterministic Finite Automata ke
Deterministic Finite Automata
Dari sebuah mesin Non-deterministic Finite Automata dapat dibuat mesin
Deterministic Finite Automata-nya yang ekuivalen. Ekuivalen disini artinya
menerima bahasa yang sama. Meskipun yang satu adalah Non-deterministic dan yang
satunya Deterministic namun keduanya menerima bahasa yang sama.
Contoh :
Sebagai contoh, akan dibuat Deterministic Finite Automata dari Non-Deterministic Finite Automata sebagai berikut :
Buatlah tabel transisinya
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}.
Ekuivalensi 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.
Ekuivalensi 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}
Ekuivalensi Non-Deterministic Automata (NFA) ke Deterministic Finite Automata (DFA).
Tidak ada komentar:
Posting Komentar