非決定性有限オートマトン
M {\displaystyle \mathbf {M} } が M = ( S , Σ , T , s 0 , A ) {\displaystyle \mathbf {M} =(S,\Sigma ,T,s_{0},A)} で構成される NFA で、 X {\displaystyle X} が Σ {\displaystyle \Sigma } に含まれる文字で構成された文字列とする。 M {\displaystyle \mathbf {M} } が文字列 X {\displaystyle X} を受容するのは、以下の条件が成立した場合である。まず、 X {\displaystyle X} を x 1 , x 2 ⋯ x n , x i ∈ ( Σ ∪ ε ) {\displaystyle x_{1},x_{2}\cdots x_{n},x_{i}\in (\Sigma \cup {\varepsilon })} と表したときに、これを入力された M {\displaystyle \mathbf {M} } がとる状態遷移が r 0 , r 1 , ⋯ , r n , r i ∈ S {\displaystyle r_{0},r_{1},\cdots ,r_{n},r_{i}\in S} のようになるとき、以下の条件が成り立つ。