Materi 5

EKUIVALENSI DFA KE NFA

Dari sebuah mesin Non-Deterministic Finite Automata dapat dibuat mesin Deterministic Finite Automata-nya yang ekuivalen (bersesuaian). Ekuivalen di sini artinya mampu menerima bahasa yang sama. 

Contoh soal 1

Buatlah DFA yang ekuivalen dengn NFA dibawah ini!

Pertama, 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 mejadi state {q0,q1}.

State {qo} bila memperoleh input 1 menjadi state {q1}.

Ekivalensi Non-Deterministic Finite 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} ε {qo,q1}

        = {q0,q1} ε ∅

        = {q0,q1}

δ{q0,q1},0) =  {q0,0} ε {qo,q1}

        = {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 paa himpunan kosong mengarah ke state himpunan kosong.

Ekivalensi Non-Deterministic Finite 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 statenya adalah semua state yang ada hubungannya dengan q1 yaitu {q0,q1} dab {q1}

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