状態遷移表
例としてマシンMの状態遷移表と状態遷移図を示す。
想定される全ての入力が表のカラムに列挙されている。想定される全ての状態は行に列挙されている。上記の状態遷移表を見れば、マシンが q0(一行目)の状態のとき 1 が入力されると、マシンは q0 状態になる。0 が入力されると q1 状態になることが二番目のカラムを見ればわかる。状態遷移図では、q0 から q1 への矢印に 0 が付記されているのがそれを表している。
非決定性有限オートマトン(NFA)の場合、ある入力によって遷移する先として複数の状態がありうる(そのため非決定性と言う)。これを状態遷移表で表すときは、括弧 { }で囲んで可能性のある全ての状態を列挙する。以下はその例である。
この非決定性マシンでは、S1 状態で 0が入力されたとき、S2 と S3 というふたつの状態を取りうる。最後のカラムは特殊な文字 ε が入力されたときの遷移を示している。これは実は入力がないときの NFA の状態遷移を意味している。このNFAは、S3 状態では入力文字を受け付けることなく S1 に遷移する可能性がある。以上のような場合があるため、この有限オートマトンは非決定性であると言える。