EKUIVALENSI NFA TO DFA

Dari suatu mesin Non Deterministic Finite Automata (NFA) dapat dikonversi atau dibuat menjadi suatu mesin Deterministic Finite Automata (DFA) yang memiliki kemampuan menerima Bahasa yang sama (ekuivalen).

Contoh soal dari ekuivalensi NFA to DFA:

1. buatlah DFA yang ekuivalen dengan NFA disanping!

untuk menyelesaikannya step pertama yang harus dilakukan adalah membuat tabel transisinya.

Lalu langkah kedua membuat tupel dari tabel transisi di atas.

δ  = {q0 , q1}

Ʃ = {0 , 1}

s =  q0

f =  q1

Dimulai dengan membuat DFA start dari state awal yaitu q0

State {q0} bila memperoleh input 0 menjadi state {q0, q1}.

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

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. 

Terakhir untuk menentukan final state pada DFA ini adalah dengan melihat NFA yang ekuivalen dengan DFA ini yaitu soal awal, diketahui Bahwa final state adalah q1,jadi pada DFA,final statenya adalah semua state yang ada hubungannya dengan q1 yaitu {q0,q1} dan {q1}