Ekuivalensi dari NFA ke DFA

    Ekuivalen artinya sama, pada bahasan materi ini artinya dapat menerima string yang sama baik itu menggunakan mesin Non-Deterministc Finite Automata (NFA) maupun Deterministc Finite Automata (DFA). Sebuah mesin Non-Deterministc Finite Automata (NFA) dapat dibuat menjadi mesin Deterministic Finite Automata(DFA) yang dapat menerima string yang sama. Ada beberapa tahap yang dapat ditempuh untuk melakukan ekuivalensi Non-Deterministc Finite Automata (NFA) ke Deterministc Finite Automata (DFA) : 

1. Buat tabel transisi dari Non-Deterministc Finite Automata (NFA) 
2. Telusuri state berikutnya dengan memanfaatkan tabel transisi ditambah dengan state { } 
3. Tentukan finish baru jika ada, dengan melihat seluruh state yang mengandung finish awal. 

Contoh kasus diberikan gambar Non-Deterministc Finite Automata (NFA) berikut : 

Diketahui : 

Q = {qo,q1} 

Σ = {0,1} 

S = q0 

F = {q1}

Buatlah Deterministic Finite Automata yang ekuivalen dengan Non-Deterministic Finite Automata diatas. 

Jawab : 

1. Buat tabel transisi dari Non-Deterministc Finite Automata (NFA)

2. Telusuri state berikutnya dengan memanfaatkan tabel transisi ditambah dengan state { }

3. Tentukan finish baru jika ada, dengan melihat seluruh state yang mengandung finish awal.

4. Gambar Deterministic Finite Automata :