Dari mesin Non Deterministic Finite Automata (NDFA) dapat dibuat mesin Deterministic Finite Automa (DFA) yang ekivalen (bersesuaian). Definisi ekivalin disini artinya mampu menerima bahasa yang sama.
Berikut ini kita akan membuat DFA yang ekivalen dengan NDFA.
Pertama-tama yang kita lakukan adalah membuat tabel transisi NFA tersebut.
Bila diketahui ∑ = {0,1}
Kita mulai dengan state awal, kemudian mengikuti transisinya membentuk state-state baru, untuk setiap state yang terbetuk diikuti lagi transisinya sampai tercover semua.
State {q0} bila memperoleh input 0 menjadi {q0,q1}
State {q0} bila memperoleh input 1 menjadi {q1}
Selanjutnya kita telusuri state-state baru yang terbentuk:
- State {q1) bila memperoleh input 0 menjadi state ø
- State {q1} bila memperoleh input 1 menjadi sate {q0,q1}
- State {q0,q1} bila memperoleh input 0 menjadi sate {q0,q1}, ini diperoleh dari δ(q0,0) = {q0,q1} digabungkan dengan δ(q1,0) = ø, maka hasilnya δ({q0,q1},0) = {q0,q1}
- State {q0,q1} bila memperoleh input 1 menjadi sate {q0,q1}, ini diperoleh dari δ(q0,1) = {q1} digabungkan dengan δ(q1,1) = {q0.q1}, maka hasilnya δ({q0,q1},1) = {q0,q1}
Perhatikan state yang sama cukup ditulis sekali saja
Hasilnya:
Hasil setelah penelusuran {q1} dan {q0,q1}, perhatikan q1 setelah menerima 0 menjasi sate ø, disini ø digambarkan sebagai state.
Selanjutnya semua state sudah kita telusuri/dirunut, tinggal state ø. State ø menerima input 0 atau 1 menjadi state ø atau δ(ø,0) = ø dan δ(ø,1) = ø.
Hasil setelah semua ditelusuri:
Pada mesin NDFA semula, himpunan state akhir adalah {q1} maka pada DFA hasil perubahannya state-state akhir adalah semua state yang mengandung {q1}. Maka state akhirnya sekarang adalah state {q1} dan state {q0,q1} atau secara formal F = {{q1},{q0,q1}}.
Hasil semua setelah ditelusuri:
Bila diketahui NDFA gambar semula menerima ‘001’ maka seharusnya DFA hasil peneluran menerima string yang sama.
δ(q0,001) = δ({q0,1},01) = δ({q0,q1},1) = {q0,q1}