Niedeterministyczne automaty skończone (NFA) Zamiast automatu deterministycznego można też użyć niedeterministycznego – różni się on tym, że ten sam stan aktualny i znak odczytany mogą go przeprowadzić w wiele różnych stanów – funkcja przejścia zmienia się w relację przejścia. Automat taki akceptuje słowo, jeśli jest w stanie dojść do stanu akceptującego. Być może dane słowo generowało też wiele innych ciągów stanów, które nie prowadziły do stanu akceptującego – nie ma to znaczenia w kwestii akceptacji.
Automaty deterministyczne są szczególnym przypadkiem automatów niedeterministycznych – zawsze możliwe jest w nich tylko jedno przejście – każde słowo generuje więc tylko jeden ciąg stanów, i kryteria akceptacji upraszczają się do kryteriów dla DFA.
Wydawać by się mogło, że NFA powinny być silniejsze od DFA.