Contoh Soal DFA
Daftar Isi [Tampilkan]
Ekuivalensi Non-Deterministic Automata (NFA) ke Deterministic Finite Automata (DFA)
Ekuivalensi NFA ke DFA
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.
 |
| Ekivalensi Non-Deterministic Automata (NFA) ke Deterministic Finite Automata (DFA) |
Contoh soal 1
Buatlah DFA yang ekuivalen dengan NFA disamping!
Kedua kita buat tupel dari tabel tersbut 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}.
δ({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.
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)
|
