Konversi dari NFA ke DFA

Konversi dari NonDeterministic Finite Automata (NFA) ke Deterministic Finite Automata (DFA)

Contoh soal :

Buatlah DFA yang Equevalen dengan NFA berikut ini :

  

Konfigurasi NFA secara formal adalah sebagai berikut :

Q = {q0, q1 }

S = {a, b}

S = q0

F = {q1}

  

Fungsi-fungsi transisinya sebagai berikut :

d (q0, a) = {q0,q1},     

d (q0, b) = q1, 

d (q1, a) = q1,             

d (q1, b) = q1,

Jika disajikan dalam tabel transisi :

d	a	b
q0	{q0,q1}	{q1}
q1	{q1}	{q1}

Konversi dari NFA ke DFA

Berdasarkan tabel transisi pada NFA, kita gambarkan diagram transisi DFA nya terlebih dahulu .

Kemudian tentukan arah dua busur keluar untuk State {q0,q1} yaitu busur arah ‘a’ dan ‘b’. Hal ini karena untuk DFA masing masing state harus memiliki pasangan busur, dalam soal ini busur ‘a’ dan ‘b’.

Busur arah ‘a’ :

d ({q0,q1}, a)   = {q0,a} È {q1,a}

                        = {q0,q1} È {q1}

                        = {q0,q1}

Busur arah ‘b’ :

d ({q0,q1}, b)   = {q0,b} È {q1,b}

                        = {q1} È {q1}

                        = {q1}

Selanjutnya menentukan state akhir, yaitu kita ingat bahwa F = {q1} ketika masih NFA maka himpunan state akhir (F) sekarang adalah semua yang mengandung state q1. 

Maka, F = {{q1}, {q0, q1}}

Gambar Diagram Transisi Akhir setelah di konversi ke DFA