Materi Non finite Automata

• NFA (Non Deterministic Finite Automata)

FA di dalam menerima input mempuyai lebih dari satu busur keluar atau tidak punya busur keluar.

Definisi Formal NFA

• NFA dinyatakan oleh 5 tuple

M=(Q , Σ , δ , q₀ , F )

▫ Q = himpunan state

▫ Σ = himpunan simbol input

▫ δ = fungsi transisi

▫ q0 = state awal / initial state

▫ F = state akhir

contoh

• G = ({q0 , q1 , q2 , q3, q4 }, {0,1}, δ , q0 , { q2 , q4}}

• Sebuah NFA menerima string, jika:

Komputasi pada NFA menerima string.

Komputasi adalah :Seluruh inputan dimasukkan dan automata dimulai dari state awal menuju ke state akhir

• Sebuah NFA Menolak string, jika:

Tidak ada komputasi pada NFA yang menerima string.

Untuk setiap komputasi: seluruh inputan selesai dimasukkan dan automata tidak sampai pada State akhir.

Atau..

• Inputan belum selesai dimasukkan dan tidak terjadi transisi