Automi finiti non deterministici (NFA)

Definizione di Automi finiti non deterministici

In informatica teorica gli automi a stati finiti non deterministici (o DFA) sono modelli di automi che soddisfano la condizione di non determinismo, cioè per ogni coppia di stato e simbolo in ingresso, esistono più transizioni possibili allo stato successivo.

Può essere immaginato come un albero di possibilità dove la radice dell’albero corrisponde all’inizio della computazione e ad ogni punto di ramificazione corrisponde a un punto nella computazione.

Definizione formale

Un NFA è definito formalmente come una quintupla , dove:

1. è l’insieme finito degli stati dell’automa.
2. è l’alfabeto finito di simboli di input.
3. è la funzione di transizione, dove è l’insieme delle parti di . In altre parole, mappa coppie di uno stato e un simbolo di input o la stringa vuota () a un insieme di possibili stati successivi.
4. è lo stato iniziale dell’automa, .
5. è l’insieme degli stati accettanti o finali dell’automa, .

Ogni transizione è un insieme di possibili stati successivi quando l’automa si trova nello stato e legge il simbolo a, dove a può essere un simbolo dell’alfabeto di input la stringa vuota ().

Come funziona?

1. L’automa riceve i simboli della stringa di input uno alla volta.
2. Per ogni simbolo letto, l’automa può transire da uno stato all’altro seguendo tutte le possibili transizioni indicate dalla funzione di transizione.
3. Se alla fine dell’input l’automa si trova in almeno uno degli stati accettanti, la stringa è accettata; altrimenti, è rifiutata.

La chiave del non determinismo sta nel fatto che più transizioni possono essere possibili per una stessa combinazione di stato e simbolo di input, l’automa esplora tutte queste possibilità in parallelo.

Non determinismo

Il non determinismo può essere visto come una specie di computazione parallela dove “processi” multipli indipendenti possono essere eseguiti contemporaneamente: esistono diverse scelte per lo stato successivo in ogni punto.

Automi finiti non deterministici generalizzati

Sono automi finiti non deterministici quando gli archi delle transizioni possono avere espressioni regolari come etichette, invece che solo elementi dell’alfabeto o “insieme vuoto”. Il GNFA legge blocchi di simboli dall’input e non necessariamente solo un simbolo alla volta come negli NFA.