Teori otomata

Otomata berhingga non-deterministik (NFA - "Nondeterministic Finite Automata") berbeda dengan DFA dalam hal fungsi transisinya:
Fungsi transisi dalam NFA memetakan pasangan formula_2 dan formula_3 kepada himpunan kuasa dari Q. Fungsi transisi yang didefinisikan seperti ini memungkinkan suatu simbol masukan untuk mengakibatkan transisi dari sebuah "state" ke beberapa kemungkinan "state" yang lain.