Ekivalensi Non Deterministic Finite Automata dengan Deterministic Finite Automata

     Dari sebuah NFA dapat dibuat bentuk DFA nya yang ekivalen (bersesuaian). Ekivalen disini artinya mampu memproduksi atau menerima bahasa yang sama. Adapun tahap pembuatan DFA yang ekivalen dari suatu NFA adalah sebagai berikut:

Contoh 4  Diketahui NFA sebagai berikut

Konfigurasi NFA contoh 4 secara formal adalah sebagai berikut :

Q = {q0, q1 }

S = {0, 1}

S = q0

F = {q1}

Tabel transisinya :

d	0	1
q0	{q0, q1}	{q1}
q1	Ø	{q0, q1}

Telusuri state berikutnya :  (d = teta)

·               d (q0, 0) = {q0, q1 }

·               d (q0, 1) = {q1}

Hasilnya : 

-                Selanjutnya telusuri untuk setiap state baru yang terbentuk :

·               d (q1, 0) = Ø

·               d (q1, 1) = {q0, q1}

·               d ({q0,q1}, 0) = {q0, q1} adalah hasil gabungan dari

d (q0, 0) = {q0, q1}dengan d (q1, 0) = Ø

·               d ({q0,q1}, 1) = {q0, q1} adalah hasil gabungan dari

d (q0, 1) = {q1}dengan d (q1, 0) = {q0, q1}

Hasilnya  :

-                Selanjutnya telusuri state baru yang terbentuk :

·               d (Ø, 0) = Ø

·               d (Ø, 0) = Ø

Hasilnya :

 

-                Selanjutnya kita ingat bahwa F = {q1} maka himpunan state akhir (F) sekarang adalah semua yang mengandung state q1. 

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

Hasilnya :