Automa a stati finiti non deterministico
Da Wikipedia, l'enciclopedia encyclopedia
Nella teoria del calcolo, un automa a stati finiti non deterministico (ASFND, in inglese nondeterministic finite automaton, NFA) è una macchina a stati finiti dove per ogni coppia stato-simbolo in input possono esservi più stati di destinazione.
Al contrario degli automi a stati finiti deterministici, gli NFA possono cambiare stato indipendentemente dal simbolo letto, tramite epsilon-transizioni. Gli automi che presentano questo tipo di transizioni sono anche detti ε-NFA.