非決定性有限オートマトン
r 0 = s 0 {\displaystyle r_{0}=s_{0}}
r i ∈ T ( r i − 1 , x i ) for i = 1 , ⋯ , n {\displaystyle r_{i}\in T(r_{i-1},x_{i}){\text{ for }}i=1,\cdots ,n}
r n ∈ A {\displaystyle r_{n}\in A}
マシンは初期状態 s 0 {\displaystyle s_{0}} から開始され、入力文字列を読み込む。オートマトンは遷移関数 T {\displaystyle T} に現在状態と入力文字(あるいは空の文字)を与えて次に遷移すべき状態を得る。しかし、NFA の次の状態は現在の入力イベントのみで決定されるのではなく、その後の任意個数の入力イベント(文字列)にも影響され、NFAが影響される入力イベントが続く限り、次の遷移先を決定することはできない。オートマトンが読み込みを終了したときに受容状態にあれば、NFA はその入力文字列を受容したと言える。さもなくば、その入力文字列は拒否されたと見なされる。
ある NFA が受容する文字列全体の集合が NFA の受容する言語である。この言語は正規言語の範囲に一致する。
任意の NFA には、それと同じ言語を受容する決定性有限オートマトン(DFA)が存在する。実用的なオートマトンを得るために、しばしば NFA は DFA に変換される。
NFA を DFA に変換するには、NFA における上述した P ( S ) {\displaystyle P(S)} の各要素を、DFA における 1状態とすればよい。この変換は部分集合構成法という。しかし最悪の場合、この変換により必要な状態数が指数関数的に増大する。