非決定性有限オートマトン
以下では、1 および 0 を入力文字とする NFA M {\displaystyle \mathbf {M} } を例として示す。 M {\displaystyle \mathbf {M} } は入力文字列に偶数個の 0 がある場合(最終状態 S 1 {\displaystyle S_{1}} )と、偶数個の 1 がある場合(最終状態 S 3 {\displaystyle S_{3}} )を受容する。
M = ( S , Σ , T , s 0 , A ) {\displaystyle \mathbf {M} =(S,\Sigma ,T,s_{0},A)} において、
{ Σ = { 0 , 1 } S = { S 0 , S 1 , S 2 , S 3 , S 4 } s 0 = S 0 A = { S 1 , S 3 } T {\displaystyle {\begin{cases}\Sigma =\{0,1\}\\S=\{S_{0},S_{1},S_{2},S_{3},S_{4}\}\\s_{0}=S_{0}\\A=\{S_{1},S_{3}\}\\T\end{cases}}}
遷移関数 T は以下の状態遷移表で定義される。