非決定性有限オートマトン

オートマトン理論では、有限状態機械は決定性有限オートマトン（DFA）と呼ばれる。

• それぞれの遷移は、そのソース状態と入力シンボルによって一意に決定され、
• 状態遷移ごとに入力シンボルの読み取りが必要です。

非決定性有限オートマトン( NFA )、または非決定性有限状態マシンは、これらの制限に従う必要はありません。特に、すべての DFA は NFA でもあります。NFA という用語は、 DFA ではないNFA を指す狭い意味で使用されることもありますが、この記事ではそうではありません。

サブセット構築アルゴリズムを使用すると、各NFAは同等のDFA、つまり同じ形式言語を認識するDFAに変換できます。^[1] DFAと同様に、NFAは通常の言語のみを認識します。

NFAは1959年にマイケル・O・ラビンとダナ・スコットによって導入され、^{[2] DFAとの同等性も示されました。NFAは}正規表現 の実装に使用されます。トンプソンの構築は、正規表現を文字列のパターンマッチングを効率的に実行できるNFAにコンパイルするアルゴリズムです。逆に、クリーネのアルゴリズムは、 NFAを正規表現（そのサイズは一般に入力オートマトンで指数関数的になります）に変換するために使用できます。

NFA は、ε 移動を伴う非決定性有限オートマトン、有限状態トランスデューサ、プッシュダウン オートマトン、交代オートマトン、ω オートマトン、確率オートマトンなど、さまざまな方法で一般化されています。DFA の他に、NFA の特殊なケースとして、一義的有限オートマトン(UFA) と自己検証有限オートマトン(SVFA) が知られています。

NFA の動作を記述する方法は、少なくとも 2 つあります。最初の方法は、NFA の非決定性を利用します。入力シンボルごとに、NFA は、すべての入力シンボルが消費されるまで新しい状態に遷移します。各ステップで、オートマトンが非決定的に適用可能な遷移の 1 つを「選択」します。少なくとも 1 つの「ラッキー ラン」、つまり、入力を完全に消費した後に受け入れ状態につながる選択シーケンスが存在する場合、それが受け入れられます。それ以外の場合、つまり、すべての入力^[3]を消費して受け入れ状態につながる選択シーケンスがまったくない場合、入力は拒否されます。^{[4] [5] : 319  [6]}

2 番目の方法では、NFA は入力シンボルの文字列を 1 つずつ消費します。各ステップで、2 つ以上の遷移が適用可能な場合は、NFA は適切な数のコピーに自分自身を「複製」し、それぞれが異なる遷移に従います。適用可能な遷移がない場合、現在のコピーは行き止まりになり、「死」ます。入力全体を消費した後、コピーのいずれかが受け入れ状態にある場合、入力は受け入れられ、それ以外の場合は拒否されます。^{[4] [7] [6]}

正式な定義のより基本的な紹介については、オートマトン理論を参照してください。

NFAは、 5つの要素から成る 組、によって正式に表現されます。${\displaystyle (Q,\Sigma ,\delta ,q_{0},F)}$

• 有限の状態集合、${\displaystyle Q}$
• 入力シンボル の有限集合、${\displaystyle \Sigma }$
• 遷移関数 : 、${\displaystyle \delta}$${\displaystyle Q\times \Sigma \rightarrow {\mathcal {P}}(Q)}$
• 初期（または開始）状態、および${\displaystyle q_{0}\in Q}$
• 受け入れ状態（または最終状態）として区別される一連の状態。${\displaystyle F}$ ${\displaystyle F\subseteq Q}$

ここで、は の冪集合を表します。 ${\displaystyle {\mathcal {P}}(Q)}$${\displaystyle Q}$

NFA が与えられた場合、認識される言語は で表され、によって受け入れられるアルファベット上のすべての文字列の集合として定義されます。 ${\displaystyle M=(Q,\Sigma ,\delta ,q_{0},F)}$${\displaystyle L(M)}$${\displaystyle \Sigma }$${\displaystyle M}$

上記の非公式な説明に大まかに対応して、によって受け入れられる文字列の同等の正式な定義がいくつかあります。 ${\displaystyle w=a_{1}a_{2}...a_{n}}$${\displaystyle M}$

• ${\displaystyle w}$は、次のような状態のシーケンス が存在する場合に受け入れられます。 ${\displaystyle r_{0},r_{1},...,r_{n}}$${\displaystyle Q}$
  1. ${\displaystyle r_{0}=q_{0}}$
  2. ${\displaystyle r_{i+1}\in \delta (r_{i},a_{i+1})}$、 のために${\displaystyle i=0,\ldots ,n-1}$
  3. ${\displaystyle r_{n}\in F}$。

言葉で言えば、最初の条件は、マシンが開始状態 から開始することを意味します。2 番目の条件は、文字列 の各文字が与えられると、マシンは遷移関数 に従って状態から状態に遷移することを意味します。最後の条件は、 の最後の入力によってマシンが受け入れ状態の 1 つで停止した場合、マシンは を受け入れることを意味します。が に受け入れられるためには、すべての状態シーケンスが受け入れ状態で終了する必要はなく、1 つで十分です。そうでない場合、つまりに従ってから の状態に移行することがまったく不可能である場合、オートマトンが文字列を拒否すると言われます。 が受け入れる文字列の集合はが認識する言語であり、この言語は で表されます。^{[5] : 320  [8]}${\displaystyle q_{0}}$${\displaystyle w}$${\displaystyle \delta }$${\displaystyle w}$${\displaystyle w}$${\displaystyle w}$${\displaystyle M}$${\displaystyle q_{0}}$${\displaystyle F}$${\displaystyle w}$${\displaystyle M}$ ${\displaystyle M}$${\displaystyle L(M)}$

• あるいは、が次のように再帰的に定義される場合、が受け入れられます。 ${\displaystyle w}$${\displaystyle \delta ^{*}(q_{0},w)\cap F\not =\emptyset }$${\displaystyle \delta ^{*}:Q\times \Sigma ^{*}\rightarrow {\mathcal {P}}(Q)}$
  1. ${\displaystyle \delta ^{*}(r,\epsilon )=\{r\}}$は空の文字列であり、${\displaystyle \epsilon }$
  2. ${\displaystyle \delta ^{*}(r,xa)=\bigcup _{r'\in \delta ^{*}(r,x)}\delta (r',a)}$すべてに対して。${\displaystyle x\in \Sigma ^{*},a\in \Sigma }$

言葉で言えば、は文字列を消費することで状態から到達可能なすべての状態の集合である。文字列は、開始状態からを消費することで の受け入れ状態に到達できる場合に受け入れられる。^{[9] [10]}${\displaystyle \delta ^{*}(r,x)}$${\displaystyle r}$${\displaystyle x}$${\displaystyle w}$${\displaystyle F}$${\displaystyle q_{0}}$${\displaystyle w}$

上記のオートマトン定義では、単一の初期状態を使用していますが、これは必須ではありません。NFA は、初期状態のセットを使用して定義される場合もあります。複数の初期状態を持つ NFA を単一の初期状態を持つ NFA に変換する簡単な構成があり、便利な表記法が提供されます。

バイナリ アルファベットを持つ次のオートマトン は、入力が 1 で終わるかどうかを判断します。遷移関数は次の状態遷移表によって定義できます(左上の図を参照)。 ${\displaystyle M}$${\displaystyle M=(\{p,q\},\{0,1\},\delta ,p,\{q\})}$${\displaystyle \delta }$

集合には複数の状態が含まれるため、は非決定的です。 の言語は、正規表現によって与えられる正規言語によって記述できます。 ${\displaystyle \delta (p,1)}$${\displaystyle M}$${\displaystyle M}$ (0|1)*1

入力文字列「1011」のすべての可能な状態シーケンスは、下の図に示されています。1つの状態シーケンスが上記の定義を満たしているため、文字列は受け入れられます。他のシーケンスが満たさなくても問題ありません。この図は、いくつかの方法で解釈できます。 ${\displaystyle M}$

• 上記の「ラッキーラン」の説明では、図の各パスは の選択のシーケンスを表します。${\displaystyle M}$
• 「クローン作成」の説明では、各縦列は特定の時点でのすべてのクローンを示し、ノードから複数の矢印が出ている場合はクローン作成を示し、矢印が出ていないノードはクローンの「死」を示します。${\displaystyle M}$

同じ図を 2 つの方法で読み取ることが可能であるということは、上記の両方の説明が同等であることを示しています。

• 上記の正式な定義の最初のものを考慮すると、「1011」は、読み取り時に状態シーケンスをトラバースする可能性があり、条件 1 から 3 を満たすため、受け入れられます。${\displaystyle M}$${\displaystyle \langle r_{0},r_{1},r_{2},r_{3},r_{4}\rangle =\langle p,p,p,p,q\rangle }$
• 2 番目の正式な定義に関して、ボトムアップ計算により、 、したがって、したがって、したがって、したがって であることが示されます。このセットは と分離していないため、文字列 "1011" が受け入れられます。${\displaystyle \delta ^{*}(p,\epsilon )=\{p\}}$${\displaystyle \delta ^{*}(p,1)=\delta (p,1)=\{p,q\}}$${\displaystyle \delta ^{*}(p,10)=\delta (p,0)\cup \delta (q,0)=\{p\}\cup \{\}}$${\displaystyle \delta ^{*}(p,101)=\delta (p,1)=\{p,q\}}$${\displaystyle \delta ^{*}(p,1011)=\delta (p,1)\cup \delta (q,1)=\{p,q\}\cup \{\}}$${\displaystyle \{q\}}$

対照的に、文字列「10」は によって拒否されます(その入力のすべての可能な状態シーケンスは右上の図に示されています)。これは、最後の 0 記号を読み取ることによって、唯一の受け入れ状態 に到達する方法がないためです。最初の「1」を消費した後 に到達できますが、これは入力「10」が受け入れられることを意味するのではなく、入力文字列「1」が受け入れられることを意味します。 ${\displaystyle M}$${\displaystyle q}$${\displaystyle q}$

決定性有限オートマトン( DFA) は、各状態とシンボルに対して遷移関数が正確に 1 つの状態を持つ特殊な種類の NFA と見なすことができます。したがって、DFA で認識できるすべての形式言語は、NFA でも認識できることは明らかです。

逆に、各 NFA に対して、同じ形式言語を認識する DFA が存在します。DFA は、べき集合構築を使用して構築できます。

この結果は、NFA は柔軟性が増しているにもかかわらず、一部の DFA が認識できない言語を認識できないことを示しています。これは、構築しやすい NFA をより効率的に実行可能な DFA に変換する上でも実用上重要です。ただし、NFA にn個の状態がある場合、結果として得られる DFA は最大 2 ⁿ個の状態を持つ可能性があり、大規模な NFA では構築が非現実的になることがあります。

ε 移動を伴う非決定性有限オートマトン (NFA-ε) は、NFA をさらに一般化したものです。この種のオートマトンでは、遷移関数が空の文字列ε に対して追加で定義されます。入力シンボルを消費しない遷移は ε 遷移と呼ばれ、状態図では「ε」というラベルの付いた矢印で表されます。ε 遷移は、現在の状態が正確にわかっていないシステムをモデル化する便利な方法を提供します。つまり、システムをモデル化していて、現在の状態 (何らかの入力文字列を処理した後) が q であるか q' であるかが明確でない場合は、これら 2 つの状態の間に ε 遷移を追加して、オートマトンを両方の状態に同時に配置することができます。

NFA -εは、5つの組、、によって 形式的に表現され、${\displaystyle (Q,\Sigma ,\delta ,q_{0},F)}$

• 有限の状態集合 ${\displaystyle Q}$
• アルファベットと呼ばれる入力記号の有限集合 ${\displaystyle \Sigma }$
• 遷移関数 ${\displaystyle \delta :Q\times (\Sigma \cup \{\epsilon \})\rightarrow {\mathcal {P}}(Q)}$
• 初期（または開始）状態${\displaystyle q_{0}\in Q}$
• 受け入れ状態（または最終状態）として区別される一連の状態。${\displaystyle F}$ ${\displaystyle F\subseteq Q}$

ここで、はのべき集合を表し、 は空の文字列を表します。 ${\displaystyle {\mathcal {P}}(Q)}$${\displaystyle Q}$${\displaystyle \epsilon }$

状態 に対して、遷移関数 の ε-遷移に従うことによってから到達可能な状態の集合を で表すとします。つまり、 次のような 状態のシーケンスがある場合、${\displaystyle q\in Q}$${\displaystyle E(q)}$${\displaystyle q}$${\displaystyle \delta }$${\displaystyle p\in E(q)}$${\displaystyle q_{1},...,q_{k}}$

• ${\displaystyle q_{1}=q}$、
• ${\displaystyle q_{i+1}\in \delta (q_{i},\varepsilon )}$それぞれについて、${\displaystyle 1\leq i<k}$
• ${\displaystyle q_{k}=p}$。

${\displaystyle E(q)}$は、 のイプシロン閉包（またはε-閉包）として知られています。 ${\displaystyle q}$

NFA の状態集合の ε 閉包は、次の ε 遷移で任意の状態から到達可能な状態の集合として定義されます。正式には、 に対して を定義します。 ${\displaystyle P}$${\displaystyle P}$${\displaystyle P\subseteq Q}$${\displaystyle E(P)=\bigcup \limits _{q\in P}E(q)}$

ε 移動のない NFA と同様に、NFA-ε の遷移関数は文字列に拡張できます。非公式には、状態から開始して文字列を読み取るときにオートマトンが到達した可能性のあるすべての状態の集合を表します。 関数は次のように再帰的に定義できます。 ${\displaystyle \delta }$${\displaystyle \delta ^{*}(q,w)}$${\displaystyle q\in Q}$${\displaystyle w\in \Sigma ^{*}.}$${\displaystyle \delta ^{*}:Q\times \Sigma ^{*}\rightarrow {\mathcal {P}}(Q)}$

• ${\displaystyle \delta ^{*}(q,\varepsilon )=E(q)}$、各状態について、イプシロン閉包を表します。${\displaystyle q\in Q,}$${\displaystyle E}$

非公式には、空の文字列を読み込むと、オートマトンがイプシロン閉包の任意の状態に移動する可能性があります。${\displaystyle q}$${\displaystyle q.}$

• ${\textstyle \delta ^{*}(q,wa)=\bigcup _{r\in \delta ^{*}(q,w)}E(\delta (r,a)),}$各状態の各文字列と各シンボル${\displaystyle q\in Q,}$${\displaystyle w\in \Sigma ^{*}}$${\displaystyle a\in \Sigma .}$

非公式には、文字列を読み取ることで、オートマトンを状態から再帰的に計算された集合内の任意の状態に駆動することができます。その後、シンボルを読み取ることで、オートマトンをからイプシロン閉包の任意の状態に駆動することができます。${\displaystyle w}$${\displaystyle q}$${\displaystyle r}$${\displaystyle \delta ^{*}(q,w)}$${\displaystyle a}$${\displaystyle r}$${\displaystyle \delta (r,a).}$

オートマトンが文字列を受け入れるとしたら、 ${\displaystyle w}$

${\displaystyle \delta ^{*}(q_{0},w)\cap F\neq \emptyset ,}$

つまり、読み取りがオートマトンを開始状態から^[11]の何らかの受容状態へと動かす可能性がある場合、${\displaystyle w}$${\displaystyle q_{0}}$${\displaystyle F.}$

入力に ​​0 が偶数個含まれているか、1 が偶数個含まれているかを判断する、バイナリ アルファベットを持つ NFA-ε を とします。0 個の出現は偶数個の出現でもあることに注意してください 。${\displaystyle M}$

正式な表記法では、遷移関係は次の状態遷移表によって定義されます。 $${\displaystyle M=(\{S_{0},S_{1},S_{2},S_{3},S_{4}\},\{0,1\},\delta ,S_{0},\{S_{1},S_{3}\})}$$${\displaystyle \delta }$

${\displaystyle M}$は、状態を持つ DFAと状態を持つDFA の 2 つのDFAの和集合として考えることができます。 の言語は、この正規表現によって与えられる正規言語で記述できます。 はε 移動を使用して定義しますが、 はε 移動を使用せずに定義できます。 ${\displaystyle \{S_{1},S_{2}\}}$${\displaystyle \{S_{3},S_{4}\}}$${\displaystyle M}$ ${\displaystyle (1^{*}01^{*}0)^{*}\cup (0^{*}10^{*}1)^{*}}$${\displaystyle M}$${\displaystyle M}$

NFA-ε が NFA と同等であることを示すには、まず NFA が NFA-ε の特殊なケースであることに注意し、すべての NFA-ε に対して同等の NFA が存在することを示す必要があります。

イプシロン移動を伴うNFAが与えられたとき、 NFAを定義する。 ${\displaystyle M=(Q,\Sigma ,\delta ,q_{0},F),}$${\displaystyle M'=(Q,\Sigma ,\delta ',q_{0},F'),}$

${\displaystyle F'={\begin{cases}F\cup \{q_{0}\}&{\text{ if }}E(q_{0})\cap F\neq \{\}\\F&{\text{ otherwise }}\\\end{cases}}}$

そして

${\displaystyle \delta '(q,a)=\delta ^{*}(q,a)}$上記で定義した拡張遷移関数を使用して、各状態と各シンボルに対して。${\displaystyle q\in Q}$${\displaystyle a\in \Sigma ,}$${\displaystyle \delta ^{*}}$

と の遷移関数、つまり、 とおよびそれらの文字列への拡張をそれぞれ区別する必要があります。 構築により、 にはε 遷移はありません。 ${\displaystyle M}$${\displaystyle M',}$${\displaystyle \delta }$${\displaystyle \delta ',}$${\displaystyle \delta }$${\displaystyle \delta '^{*},}$${\displaystyle M'}$

各弦について、長さに関する帰納法によって証明できる。${\displaystyle \delta '^{*}(q_{0},w)=\delta ^{*}(q_{0},w)}$${\displaystyle w\neq \varepsilon }$${\displaystyle w.}$

これに基づいて、各文字列に対して、${\displaystyle \delta '^{*}(q_{0},w)\cap F'\neq \{\}}$${\displaystyle \delta ^{*}(q_{0},w)\cap F\neq \{\},}$${\displaystyle w\in \Sigma ^{*}:}$

• これが定義から導かれるならば${\displaystyle w=\varepsilon ,}$${\displaystyle F'.}$
• それ以外の場合は、${\displaystyle w=va}$${\displaystyle v\in \Sigma ^{*}}$${\displaystyle a\in \Sigma .}$

から、私たちはまだ「」方向を示す必要があります。 ${\displaystyle \delta '^{*}(q_{0},w)=\delta ^{*}(q_{0},w)}$${\displaystyle F\subseteq F',}$$${\displaystyle \delta '^{*}(q_{0},w)\cap F'\neq \{\}\;\Leftarrow \;\delta ^{*}(q_{0},w)\cap F\neq \{\};}$$${\displaystyle \Rightarrow }$

• に状態が含まれている場合、 にはにある同じ状態が含まれています。${\displaystyle \delta '^{*}(q_{0},w)}$${\displaystyle F'\setminus \{q_{0}\},}$${\displaystyle \delta ^{*}(q_{0},w)}$${\displaystyle F}$
• が含まれている場合 、次の状態も含まれます。${\displaystyle \delta '^{*}(q_{0},w)}$${\displaystyle q_{0},}$${\displaystyle q_{0}\in F,}$${\displaystyle \delta ^{*}(q_{0},w)}$${\displaystyle F,}$${\displaystyle q_{0}.}$
• とが含まれる場合、 に状態が存在し、同じ状態が^{[12]に存在しなければならない。}${\displaystyle \delta '^{*}(q_{0},w)}$${\displaystyle q_{0},}$${\displaystyle q_{0}\not \in F,}$${\displaystyle q_{0}\in F',}$${\displaystyle E(q_{0})\cap F}$${\textstyle \delta ^{*}(q_{0},w)=\bigcup _{r\in \delta ^{*}(q,v)}E(\delta (r,a)).}$

NFA は DFA と同等であるため、NFA-ε も DFA と同等です。

NFA によって認識される言語の集合は、次の操作の下で閉じています。これらの閉包操作は、任意の正規表現から NFA を構築するThompson の構築アルゴリズムで使用されます。また、NFA が正規言語を正確に認識することを証明するためにも使用できます。

• 和集合（図参照）；つまり、言語L _{1が何らかの NFA} A ₁によって受け入れられ、言語 L _{2 が}何らかのA ₂によって受け入れられる場合、言語L ₁ ∪ L ₂を受け入れるNFA A _{u を}構築できます。
• 共通集合; 同様に、A ₁とA _2から、 L ₁ ∩ L ₂を受け入れるNFA A _{i を}構築できます。
• 連結
• 否定; 同様に、A _{1から Σ} ^* \ L ₁を受け入れるNFA A _{n を}構築できます。
• クリーネ閉鎖

NFA は ε 移動を持つ非決定性有限オートマトン (NFA-ε) と同等であるため、上記の閉包は NFA-ε の閉包特性を使用して証明されます。

マシンは指定された初期状態から開始し、アルファベットから一連の記号を読み取ります。オートマトンは現在の状態と、読み取った記号または空の文字列を使用して、状態遷移関数Δ を使用して次の状態を決定します。ただし、「NFA の次の状態は、現在の入力イベントだけでなく、任意の数の後続の入力イベントにも依存します。これらの後続イベントが発生するまで、マシンがどの状態にあるかを判断することはできません」。^[13]オートマトンが読み取りを終了したときに受け入れ状態にある場合、NFA は文字列を受け入れると言われ、そうでない場合は文字列を拒否すると言われます。

NFA が受け入れるすべての文字列の集合は、NFA が受け入れる言語です。この言語は正規言語です。

すべての NFA に対して、同じ言語を受け入れる決定性有限オートマトン(DFA) が見つかります。したがって、既存の NFA を DFA に変換して、(おそらく) より単純なマシンを実装することが可能です。これは、べき集合構築を使用して実行できますが、これにより、必要な状態の数が指数関数的に増加する可能性があります。べき集合構築の正式な証明については、べき集合構築の記事を参照してください。

NFA を実装する方法は多数あります。

• 同等のDFAに変換する。場合によっては、状態数が指数関数的に増加する可能性がある。^[14]
• NFA が現在ある可能性のあるすべての状態の集合データ構造を保持する。入力シンボルの消費時に、すべての現在の状態に適用された遷移関数の結果を結合して、次の状態のセットを取得する。ε 移動が許可されている場合は、そのような移動によって到達可能なすべての状態を含める (ε 閉包)。各ステップでは最大s ^{2 回の}計算が必要であり、s はNFA の状態数である。最後の入力シンボルの消費時に、現在の状態の 1 つが最終状態である場合、マシンは文字列を受け入れる。長さnの文字列は、時間O ( ns ² )、^[15]および空間O ( s )で処理できる。
• 複数のコピーを作成します。n通りの決定ごとに、NFA はマシンのコピーを最大n −1 個作成します。それぞれが別の状態になります。最後の入力シンボルを消費したときに、NFA のコピーの少なくとも 1 つが受け入れ状態にある場合、NFA は受け入れます。(この場合も、NFA 状態の数に応じて線形ストレージが必要です。NFA 状態ごとに 1 つのマシンが存在する可能性があるためです。)
• NFAの遷移構造を通じてトークンを明示的に伝播し、トークンが最終状態に到達するたびに一致させます。これは、NFAが遷移を引き起こしたイベントに関する追加のコンテキストをエンコードする必要がある場合に役立ちます。（この手法を使用してオブジェクト参照を追跡する実装については、Tracematchesを参照してください。）^[16]

• NFA の空性問題、つまり、与えられた NFA の言語が空であるかどうかをチェックする問題は、線形時間で解決できます。これを行うには、初期状態から深さ優先探索を実行し、ある最終状態に到達できるかどうかを確認するだけです。
• NFAが与えられた場合、それが普遍的であるかどうか、つまりそれが受け入れない文字列があるかどうかをテストすることはPSPACE完全である。 ^[17]結果として、包含問題、つまり2つのNFAが与えられた場合、一方の言語は他方の言語のサブセットであるかどうかについても同じことが言える。
• NFA Aと整数nを入力として与えられた場合、長さnの単語がAにいくつ受け入れられるかを決定する問題は扱いにくく、 #P困難です。実際、この問題は複雑性クラスSpanLに対して完全です（簡約化の下で）。^[18]

NFA と DFA は、ある言語が NFA によって認識される場合は DFA でも認識され、その逆も同様であるという点で同等です。このような同等性の確立は重要かつ有用です。これは、特定の言語を認識する NFA を構築する方が、その言語の DFA を構築するよりもはるかに簡単な場合があるので有用です。これは、NFA を使用すると、計算理論における多くの重要な特性を確立するために必要な数学的作業の複雑さを軽減できるため重要です。たとえば、正規言語の閉包特性を証明するには、DFA よりも NFA を使用する方がはるか に簡単です。

• 決定論的有限オートマトン
• 双方向非決定性有限オートマトン
• プッシュダウンオートマトン
• 非決定性チューリングマシン

• Rabin, MO; Scott, D. (1959 年 4 月)。 「有限オートマトンとその決定問題」。IBM Journal of Research and Development。3 ( 2): 114–125。doi :10.1147/rd.32.0114。
• シプサー、マイケル(1997)。計算理論入門(第 1 版)。PWS 出版。ISBN 978-0-534-94728-6。（印刷物を読むのに障害のある利用者もアクセス可能）（§1.2「非決定論」、47～63ページを参照。）
• ホップクロフト、ジョン E.、ウルマン、ジェフリー D. (1979)。オートマトン理論、言語、計算入門(第 1 版)。アディソン ウェスレー。ISBN 0-201-02988-X。（印刷障害のある利用者も利用可能）
• ホップクロフト、ジョン E. ;モトワニ、ラジーブ;ウルマン、ジェフリー D. (2006) [1979].オートマトン理論、言語、計算入門(第 3 版). Addison-Wesley. ISBN 0-321-45536-3。 (第 2 章「有限オートマトン」を参照してください。)