Non Determinisme (NFA Vs DFA) ~ Teori Komputasi

Menerima: jika terdapat paling sedikit satu path yang berakhir di state Final di pohon trace eksekusi.

Menolak: jika semua path yang mungkin “terhenti” (stuck, halt) atau berakhir di state yang bukan Final.

Interpretasi:

1. NFA selalu mengambil pilihan yang benar untuk memastikan penerimaan (asumsi: path yang berakhir di state Final memang ada),
2. NFA membuat copy dirinya sendiri untuk menelusuri semua path yang mungkin,
3. NFA menjelajahi semua path secara parallel.

Untuk lebih lengkapnya silakan baca slide di bawah ini :
Tk Slides01

Posted in: komputasi