Ekuivalensi NFA (Nondeterministic Finite Automata) Ke DFA (Deterministic Finite Automata)

Dari sebuah mesin Non-deterministic Finite Automata dapat dibuat mesin DFA yang ekivalen. Ekivalen artinya mampu menerima bahasa yang sama.

Simulasi NFA ke DFA

• ·        Cara simulasi NFA ke DFA adalah dengan menbuat state DFA berkorespondensi dengan set state di NFA.
• ·        DFA yang dibentuk mencatat semua state yang mungkin pada NFA setelah membaca input tertentu.

FSA (Finite State Automata)  FSA terdiri dari :

1. DFA (Deterministic Finite Automata)

2. NFA (Non-deterministic Finite Automata) Ciri DFA dan NFA 1. Ciri DFA (Deterministic Finite Automata) 

Contoh :

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 tabel transisi dan diagram transisi untuk DFA nya :
•