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.
Sebagai contoh, akan dibuat Deterministic Finite Automata dari Non-Deterministic Finite Automata berikut.
Diketahui Σ = {0,1}
Adapun langkah-langkahnya adalah sebagai berikut.
-
Buatlah tabel transisi dari diagram transisi di atas.
-
Buatlah diagram transisi untuk finite state automata dari tabel transisi di atas. a. Kita mulai dari state awal yaitu q 0
b. Selanjutnya, kita telusuri lebih lanjut tentang q 0 , yaitu: Bila state q 0 mendapat input 0 menjadi state {q 0 ,q1 } Bila state q 0 mendapat input 1 menjadi state {q1 }, seperti yang tampak pada gbr.
c. Selanjutnya kita telusuri untuk state q1 , yaitu : Bila state q 1 mendapat input 0 maka menjadi state Ø Bila state q 1 mendapat input 1 maka menjadi state {q 0 ,q1 }, sehingga diperoleh gbr.
d. Selanjutnya kita telusuri untuk state {q0 ,q1 }, yang merupakan penggabungan dari state q 0 dan state q 1 , sehingga hasil state {q0 ,q1 } merupakan penggabungan dari hasil state q 0 dan state q1 . Bila state q 0 mendapat input 0 menjadi state {q 0 ,q1 } Bila state q 1 mendapat input 0 maka menjadi state Ø Sehingga diperoleh jika state {q 0 ,q1 } mendapat input 0 menjadi state {q 0 ,q1 }