Computazione deterministica

Quando una macchina deterministica si trova in un dato stato e legge un certo simbolo, lo stato successivo è univocamente determinato

Computazione non deterministica

Il non determinismo è una generalizzazione del determinismo

Un automa finito non deterministico (NFA) permette di avere

• 0, 1 o anche più archi uscenti per ciascun simbolo dell’alfabeto
• 0,1 o anche più archi uscenti con etichetta $\epsilon$

Come computa un NFA

Se un NFA è in uno stato e, leggendo un simbolo $a$ dell’alfabeto, si trova davanti a più scelte (più archi uscenti etichettati con $a$):

• si divide in più copie di se stesso: una copia per ciascuna scelta
• ogni copia segue la computazione in parallelo indipendentemente dalle altre

Se una copia di un NFA legge un simbolo che non si trova su alcun arco uscente da quello stato, allora quella copia della macchina muore insieme a tutto il suo ramo di computazione

Accettazione:

• se almeno una copia giunge in uno stato accettante, la stringa è accettata
• se nessuna copia giunge in uno stato accettante, allora la stringa non è accettata

Se un NFA è in uno stato con uno o più archi etichettati con $\epsilon$, si comporta come segue:

• senza leggere alcun simbolo della stringa input, la macchina si divide in più copie: una che segue ciascun arco etichettato con $\epsilon$ e una che resta nello stato corrente
• ogni copia segue la computazione in parallelo indipendentemente dalle altre

Definizione formale

Sia $\sum_\epsilon = \sum \cup \{\epsilon\}$