Ein FSA wird als NFA (non-deterministic finite automaton) bezeichnet, wenn für den Knoten eines Zustandsgraphen mehrere identische Zeichen eines Alphabets als Markierung einer wegführenden Kante auftreten. Untenstehende Abbildung veranschaulicht einen solchen NFA:
 

Die entsprechende reguläre Grammatik zu dieser NFA lautet:

        A -> aB
        A -> aC
        B -> b
        C -> a

Die Zustandsübergangsfunktion von q0 hat demzufolge zwei Möglichkeiten: (q0, a) -> q1 oder (q0, a) -> q2. Es lässt sich nicht von vornherein die korrekte Abarbeitung bestimmen. Wird der falsche Pfad gewählt, muss der Schritt rückgängig gemacht und neu begonnen werden. NFA sind daher gegenüber den DFA ineffizient. Jeder NFA lässt sich aber in einen entsprechenden DFA umwandeln. Ein NFA ist somit nicht leistungsfähiger als ein DFA.  Siehe dazu die Funktion NFA to DFA options in JFLAP.