Non-Determinictic Finite Automata (NDFA)

Non-Determinictic Finite Automata (NDFA)

Non-deterministik finite automata (NFA) bersifat non-deterministik, yang berarti bahwa automata tersebut dapat berada di beberapa state pada saat yang bersamaan atau dengan kata lain NFA dapat menebak di state mana dia berikutnya akan berada (Hopcroft et al., 2007).Pada Non-Determinaistic Finite Automata (NFA) dari suatu state bisa terdapat 0,1, atau lebih busur keluar (transisi) berlabel simbol input yang sama. Non-Determinaistic Finite Automata didefenisikan pula dengan lima(5) M=(Q , Σ , δ , S , F )dengan arti yang serupa pada Deterministic Fnite Automata. Disini perbedaan ada padafungsi transisinya, dimana untuk setiap pasangan state-input, kita bisa memiliki 0 (nol) atau lebih pilihan untuk state berikutnya.

Pada NFA dari suatu state bisa terdapat nol (0), satu (1), atau lebih busur keluar
(transisis) berlabel simbol yang sama. Jadi setiap pasangna state-input, kita bisa memiliki 0 atau lebih pilihan untuk state berikutnya.

Contoh 1 :

Pada NFA contoh 2 diatas terdapat dua busur keluar berlabel input ‘a’. Dari state q0 bila
mendapat input ‘a’ bisa berpindah ke state q0 atau q1 yang secara formal dinyatakan : δ
(q0, a) = {q0, q1}
Konfigurasi NFA contoh 2 secara formal adalah sebagai berikut :
Q = {q0, q1 }
Σ = {a, b}
S = q0
F = {q1}
Fungsi-fungsi transisinya sebagai berikut :
δ (q0, a) = {q0,q1}, δ (q0, b) = q1,
δ (q1, a) = q1, δ (q1, b) = q1,
Jika disajikan dalam tabel transisi :

* Perhatikan : Dalam cara penulisan state hasil transisi pada tabel transisi untuk NFA,
digunakan kurung kurawal ‘{‘ dan ‘}’karena hasil transisisnya merupakan suatu
himpunan state.
* Pada bagian ini dapat dilihat NFA dengan lebih dari satu pilihan state berikutnya.
Contoh 2 :

Konfigurasi NFA contoh 3 secara formal adalah sebagai berikut :
Q = {q0, q1 }
Σ = {a, b}
S = q0
F = {q1}
Fungsi-fungsi transisinya sebagai berikut :
δ (q0, a) = q1, δ (q0, b) = q0,
δ (q1, a) = q0, δ (q1, b) = Ø,
Jika disajikan dalam tabel transisi :