Existuje-li více přechodů pro daný znak, nedeterministický automat spustí více paralelních výpočtů současně.
Pokud některá z větví výpočtu příjme, pak automat slovo přijímá
Pro každý nederministicé automat N, existuje deterministický automat D, který je s nim ekvivalentní
L(D) = L(N)
w1 = 001110 = s0 s2 s1 s2 s0
w2 = 00011 = p p p p q p