Definizione di Automa a Stati Finiti non Deterministico

Un Automa a Stati Finiti non Determinstico (NDFA) e` una quintupla <Q,I,delta,q0,F>; dove:

Q e` un insieme finito di stati;
I e` un insieme finito di simboli di ingresso;
delta e` la, possibilmente parziale, funzione di tranzizione
delta:Q X I->P(Q), dove P(Q) e` l'insieme delle parti di Q;
q0 appartenente a Q e` detto stato iniziale;
F contenuto in Q e` l'insieme degli stati finali.

Un NDFA puo` dunque assumere differenti comportamenti in presenza della stessa coppia Simbolo di Ingresso/Stato.

Una stringa e` accettata da un NDFA se e solo se almeno una delle possibili sequenze di transizione che essa genera porta ad uno stato finale.

Come dispositivi di riconoscimento di linguaggi, i NDFA non sono piu` potenti degli DFA, cioe` sono equivalenti.