非決定性有限オートマトン
NFA は入力文字列を受け付ける。各入力文字を受け付ける度に新たな状態に遷移する。これが全ての文字の入力が終わるまで続く。
S 1 ⟶ c 1 S 2 ⟶ c 2 ⋯ ⟶ c n − 1 S n {\displaystyle S_{1}{\overset {c_{1}}{\longrightarrow }}S_{2}{\overset {c_{2}}{\longrightarrow }}\cdots {\overset {c_{n-1}}{\longrightarrow }}S_{n}}
非決定性と呼ばれるのは、ある状態からの遷移先が入力文字だけでは一意に定まらない場合があることと、入力文字を受け取らなくても状態遷移する場合があることからである。例えば、状態 S1 にあって文字 a が入力された場合、この文字を受け取らずに状態 S2 に遷移してから a を受け取って状態 S3 に遷移することが可能である。
S 1 ⟶ ε S 2 ⟶ a S 3 {\displaystyle S_{1}{\overset {\varepsilon }{\longrightarrow }}S_{2}{\overset {a}{\longrightarrow }}S_{3}}
入力文字を受け取らずに遷移することを「イプシロン遷移」と呼ぶ。一般にギリシャ文字を使って「ε-遷移」と記述する。状態遷移図では、入力文字の代わりに ε を付記する。
最後の入力文字を受け取ったとき、NFA がある特定の状態(受容状態)になった場合のみ、その入力文字列をNFAが受容したと判断される。一方、受容状態以外で終了した場合、その入力文字列は拒否されたと判断される。