Teknik Kompilasi : KONVERSI NFA KE 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).
Berikut contoh konversi dari Non Deterministic Finite Automata menjadi Deterministic Finite Automata:
- Berikut table transisi dan diagram transisi untuk NFA :
Dapat dilihat dari gambar di atas ada suatu state yang diberi inputan menuju ke beberapa state, yaitu S0 yang diberi inputan b bisa menuju ke S0 dan S1
- Lalu dikonversi menjadi DFA, dengan cara membuat state baru berupa gabungan dari S0 dan S1.
- Lalu untuk state {S0,S1} jika diberi inputan a maka hasilnya adalah gabungan dari hasil S0 dan S1 yang diberi inputan a yaitu {S0,S1}
- Lalu untuk state {S0,S1} jika diberi inputan b maka hasilnya adalah gabungan dari hasil S0 dan S1 yang diberi inputan b yaitu {S0,S1}
- Berikuta table transisi dan diagram transisi untuk DFA nya :
