NonDeterministic Finite Automata (NFA)

NonDeterministic Finite Automata (NFA)

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 soal :

Pada NFA 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 :

 d (q0, a) = {q0, q1}

Konfigurasi NFA secara formal adalah sebagai berikut :

Q = {q0, q1 }

S = {a, b}

S = q0

F = {q1}

Fungsi-fungsi transisinya sebagai berikut :

d (q0, a) = {q0,q1},     

d (q0, b) = q1, 

d (q1, a) = q1,             

d (q1, b) = q1,

Jika disajikan dalam tabel transisi :

d	a	b
q0	{q0,q1}	{q1}
q1	{q1}	{q1}

* 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.