決定性有限オートマトン

3の倍数の2進数のみを受け入れる決定性有限オートマトンの例。状態S ₀は開始状態であると同時に受け入れ状態でもある。例えば、文字列「1001」は状態シーケンスS ₀、S ₁、S ₂、S ₁、S ₀へとつながり、したがって受け入れられる。

理論計算機科学の一分野である計算理論において、決定性有限オートマトン（DFA）は、決定性有限アクセプタ（DFA）、決定性有限状態機械（DFSM）、または決定性有限状態オートマトン（DFSA）とも呼ばれ、与えられた記号列を、その文字列によって一意に決定される状態シーケンスを実行することによって受け入れるか拒否するかを判断する有限状態機械である。 ^{[ 1 ]}決定性とは、実行される計算が一意であることを意味する。有限状態機械を捉える最も単純なモデルを求めて、ウォーレン・マカロックとウォルター・ピッツは、1943年に有限オートマトンに類似した概念を初めて提唱した研究者の一人であった。^{[ 2 ] [ 3 ]}

この図は、状態図を使用して決定論的有限オートマトンの図を示しています。この例のオートマトンは、 S ₀、 S ₁、 S ₂の 3 つの状態があります(グラフィカルでは円で示されています)。オートマトンは、入力として有限の0 と 1 のシーケンスを受け取ります。各状態には、0 と 1 の両方について次の状態につながる遷移矢印があります。シンボルを読み取ると、DFA は遷移矢印に従って、ある状態から別の状態に決定論的にジャンプします。たとえば、オートマトンの現在の状態が S _{0にあり、現在の入力シンボルが 1 の場合、決定論的に状態 S 1}にジャンプします。DFA には、計算が始まる開始状態(グラフィカルではどこからともなく入ってくる矢印で示されています) と、計算が成功したかどうかを定義する一連の受け入れ状態(グラフィカルでは二重円で示されています) があります。

DFAは抽象的な数学的概念として定義されていますが、字句解析やパターンマッチングといった様々な具体的な問題を解決するために、ハードウェアやソフトウェアに実装されることがよくあります。例えば、DFAは、電子メールアドレスなどのオンラインユーザー入力が構文的に有効かどうかを判断するソフトウェアをモデル化することができます。^{[ 4 ]}

DFAは、ある状態から同じラベルの複数の矢印を持つ可能性のある非決定性有限オートマトン（NFA）へと一般化されています。べき集合構築法を用いることで、すべてのNFAは同じ言語を認識するDFAに変換できます。DFAとNFAは、正規言語の集合を正確に認識します。^{[ 1 ]}

正式な定義

決定性有限オートマトンMは、5つの組（Q 、 Σ、δ、q ₀、F）で構成され、

• 有限の状態集合Q
• アルファベットΣと呼ばれる入力記号の有限集合
• 遷移関数δ  : Q × Σ → Q
• 初期（または開始）状態 ${\displaystyle q_{0}\in Q}$
• 受け入れ状態（または最終状態）の集合 ${\displaystyle F\subseteq Q}$

w = a ₁ a ₂ ... a _{n を}アルファベットΣ上の文字列とする。オートマトンM は、以下の条件を満たす状態 列r ₀ , r ₁ , ..., r _nがQに存在する場合、文字列wを受け入れる。

1. r ₀ = q ₀
2. r _{i +1} = δ ( r _i , a _{i +1} )、ただしi = 0, ..., n − 1
3. ${\displaystyle r_{n}\in F}$。

言葉で言えば、最初の条件は、マシンが開始状態q ₀から開始することを意味します。2番目の条件は、文字列wの各文字が与えられたとき、マシンは遷移関数δに従って状態から状態へと遷移することを意味します。最後の条件は、wの最後の入力によってマシンがいずれかの受理状態で停止した場合、マシンはwを受け入れることを意味します。それ以外の場合、オートマトンが文字列を拒否することを意味します。Mが受け入れる文字列の集合は、 Mが認識する言語であり、この言語はL ( M )と表記されます。

受け入れ状態と開始状態を持たない決定論的有限オートマトンを、遷移システムまたは半オートマトンと呼びます。

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

例

次の例は、入力に偶数個の 0 が含まれていることを要求するバイナリ アルファベットの DFA Mです。

Mの状態図

M = ( Q , Σ, δ , q ₀ , F )ここで

• Q = { S ₁、S ₂ }
• Σ = {0, 1}
• q ₀ = S ₁
• F = { S ₁ }および
• δは次の状態遷移表によって定義されます。

	0	1
S 1	S2​	S 1
S2​	S 1	S2​

状態S ₁は、入力に0が偶数個含まれていることを表し、状態S ₂は奇数個含まれていることを示します。入力に1が含まれていても、オートマトンの状態は変化しません。入力が終了すると、状態は入力に0が偶数個含まれていたかどうかを示します。入力に0が偶数個含まれていた場合、Mは受理状態である状態S ₁で終了し、入力文字列は受理されます。

Mによって認識される言語は、正規表現によって与えられる正規言語です。ここで、 はクリーネ星で、例えば、は連続する任意の数 (ゼロの場合もある) の 1 を表します。 (1*) (0 (1*) 0 (1*))**1*

バリエーション

完全と不完全

上記の定義によれば、決定性有限オートマトンは必ず完全です。つまり、各状態から各入力シンボルの遷移を定義します。

これは最も一般的な定義ですが、一部の著者は、決定性有限オートマトンという用語を少し異なる概念で使用しています。つまり、各状態と各入力シンボルに対して最大で1つの遷移を定義するオートマトンであり、遷移関数は部分的であることが許可されています。^{[ 5 ]}遷移が定義されていない場合、このようなオートマトンは停止します。

ローカルオートマトン

ローカルオートマトンとは、必ずしも完全ではないDFAの一種であり、同じラベルを持つすべての辺が単一の頂点につながる。ローカルオートマトンには、単語の所属が単語の長さ2の「スライディングウィンドウ」によって決定されるような、ローカル言語のクラスが含まれる。 ^{[ 6 ] [ 7 ]}

アルファベットA上のマイヒルグラフは、頂点集合Aと、その頂点のサブセットに「開始」と「終了」というラベルが付けられたものを持つ有向グラフである。マイヒルグラフが受理する言語は、開始頂点から終了頂点への有向パスの集合である。したがって、グラフはオートマトンとして機能する。^{[ 6 ]}マイヒルグラフが受理する言語のクラスは、局所言語のクラスである。^{[ 8 ]}

ランダム性

開始状態と受け入れ状態を無視すると、n個の状態とサイズkのアルファベットのDFA は、すべての頂点が1, ..., kとラベル付けされたk 個の出力アークを持つn頂点の有向グラフ（k出力有向グラフ）とみなすことができます。k ≥ 2が固定の整数である場合、このようなk出力有向グラフで一様にランダムに選択された最大の強連結成分（SCC）は高い確率で線形サイズになり、すべての頂点から到達できることが知られています。^{[ 9 ]}また、 n の増加に伴ってk が増加することを許容すると、有向グラフ全体が、接続性のエルデシュ・レーニイモデルに類似した強連結性の相転移を持つことが証明されています。^{[ 10 ]}

ランダムDFAでは、1つの頂点から到達可能な頂点の最大数は、高い確率で最大SCCの頂点数に非常に近くなります。 ^{[ 9 ] [ 11 ]}これは、最小入次数1の最大誘導サブダイグラフにも当てはまり、 1コアの有向バージョンと見なすことができます。^{[ 10 ]}

閉鎖特性

左上のオートマトン（図1）は、少なくとも1回「00」を含むすべてのバイナリ文字列の言語を認識します。右下のオートマトン（図2）は、「1」が偶数個含まれるすべてのバイナリ文字列を認識します。左下のオートマトン（図3）は、前2つのオートマトン（図4）の積として得られ、両言語の共通部分を認識します。

DFAが、DFAが認識可能な言語に演算を適用することで得られる言語を認識する場合、DFAはその演算に関して閉じていると言われる。DFAは以下の演算に関して閉じている。

• 連合
• 交差点^{[ 12 ]}（写真参照）
• 連結
• 補体
• クリーネ閉鎖
• 逆転^{[ 13 ]}
• 商^{[ 13 ]}
• 代替^{[ 14 ]}
• 準同型性^{[ 13 ] [ 14 ]}

各演算について、状態数に関する最適な構成は状態複雑度研究において決定されている。DFAは非決定性有限オートマトン（NFA）と等価であるため、これらの閉包はNFAの閉包性を用いて証明することもできる。

遷移モノイドとして

与えられたDFAの連なりは、遷移関数の非常に一般的な定式化とそれ自身との合成の列と見ることができます。ここではその関数を構築します。

与えられた入力記号 に対して、すべての に対してを定義することで遷移関数を構築できます。（この方法は のカリー化と呼ばれます。）この観点から、 はQ の状態に「作用」して別の状態を生成します。次に、関数合成を様々な関数、、 などに繰り返し適用した結果を考えてみましょう。文字のペア が与えられた場合、新しい関数 を定義できます。ここで は関数合成を表します。 ${\displaystyle a\in \Sigma }$ ${\displaystyle \delta _{a}:Q\rightarrow Q}$ ${\displaystyle \delta _{a}(q)=\delta (q,a)}$ ${\displaystyle q\in Q}$ ${\displaystyle \delta _{a}}$ ${\displaystyle \delta _{a}}$ ${\displaystyle \delta _{b}}$ ${\displaystyle a,b\in \Sigma }$ ${\displaystyle {\widehat {\delta }}_{ab}=\delta _{a}\circ \delta _{b}}$ ${\displaystyle \circ }$

明らかに、このプロセスは再帰的に継続することができ、 の次の再帰定義が得られます。 ${\displaystyle {\widehat {\delta }}:Q\times \Sigma ^{\star }\rightarrow Q}$

${\displaystyle {\widehat {\delta }}(q,\epsilon )=q}$、空文字列であり、 ${\displaystyle \epsilon }$

${\displaystyle {\widehat {\delta }}(q,wa)=\delta _{a}({\widehat {\delta }}(q,w))}$、ここで、 および。 ${\displaystyle w\in \Sigma ^{*},a\in \Sigma }$ ${\displaystyle q\in Q}$

${\displaystyle {\widehat {\delta }}}$ はすべての単語 に対して定義されます。DFA のランは、 とそれ自身との合成のシーケンスです。 ${\displaystyle w\in \Sigma ^{*}}$ ${\displaystyle {\widehat {\delta }}}$

関数の繰り返し合成はモノイドを形成する。遷移関数の場合、このモノイドは遷移モノイド、あるいは変換半群と呼ばれることもある。この構成は逆のことも可能である。つまり、 が与えられたとき、 を再構成することができ、したがって2つの記述は同値である。 ${\displaystyle {\widehat {\delta }}}$ ${\displaystyle \delta }$

メリットとデメリット

DFAは、入力ストリームに対してDFAをシミュレートするための、単純な線形時間、定数空間のオンラインアルゴリズムが存在するため、最も実用的な計算モデルの一つです。また、以下の点を認識することでDFAを見つける効率的なアルゴリズムも存在します。

• 特定の DFA によって認識される言語の補語。
• 与えられた 2 つの DFA によって認識される言語の和集合/積集合。

DFA は標準形式(最小 DFA )に縮小できるため、次のことを決定するための効率的なアルゴリズムも存在します。

• DFA が文字列を受け入れるかどうか (空問題)
• DFA がすべての文字列を受け入れるかどうか (普遍性問題)
• 2つのDFAが同じ言語を認識するかどうか（等価性問題）
• DFA によって認識される言語が、2 番目の DFA によって認識される言語に含まれているかどうか (包含問題)
• 特定の正規言語における最小状態数を持つDFA（最小化問題）

DFA は計算能力の点では非決定性有限オートマトン(NFA) と同等である。これは、まず、あらゆる DFA は NFA でもあるため、NFA は DFA にできることは何でも実行できるからである。また、NFA が与えられれば、べき集合構成を使用して、NFA と同じ言語を認識する DFA を構築することができるが、DFA は NFA よりも指数的に多くの状態を持つ可能性がある。^{[ 15 ] [ 16 ]}しかし、NFA が計算上 DFA と同等であっても、上記の問題は必ずしも NFA に対しても効率的に解決されるわけではない。NFA の非普遍性問題はPSPACE 完全である。なぜなら、最短の拒否語を持つ小さな NFA が指数関数的サイズで存在するからである。DFA が普遍的であるためには、すべての状態が最終状態である必要があるが、これは NFA には当てはまらない。等式問題、包含問題、および最小化問題も、サイズが指数関数的に増大する NFA の補数を形成する必要があるため、PSPACE 完全である。^{[ 17 ]}

一方、有限状態オートマトンが認識できる言語の能力は極めて限られています。定数以上の空間で解く問題を含む多くの単純な言語は、DFAでは認識できません。DFAが認識できない単純な記述言語の典型的な例は、括弧言語、すなわち「(()())」のような適切に対になった括弧で構成される言語です。直感的に言えば、DFAはDyck言語を認識できません。なぜなら、DFAは計数できないからです。DFAのようなオートマトンには、任意の数の「現在開いている」括弧を表す状態が必要であり、つまり、無限の数の状態が必要になるからです。もう1つのより単純な例は、有限だが任意の数のaとそれに続く同数のbからなる文字列a n b nで^{構成される}言語^です。^{[ 18 ]}

ラベル付けされた単語からのDFA識別

肯定的な単語の集合と否定的な単語の集合が与えられれば、 からのすべての単語を受け入れ、 からのすべての単語を拒否するDFA を構築できます。この問題はDFA 識別（合成、学習）と呼ばれます。一部のDFA は線形時間で構築できますが、状態数が最小の DFA を識別する問題は NP 完全です。^{[ 19 ]最小 DFA 識別の最初のアルゴリズムは Trakhtenbrot と Barzdin [ 20 ]} によって提案され、 TB アルゴリズムと呼ばれています。ただし、TB アルゴリズムでは、 から指定された長さまでのすべての単語が のいずれかに含まれていると想定しています。 ${\displaystyle S^{+}\subset \Sigma ^{*}}$ ${\displaystyle S^{-}\subset \Sigma ^{*}}$ ${\displaystyle S^{+}}$ ${\displaystyle S^{-}}$ ${\displaystyle \Sigma }$ ${\displaystyle S^{+}\cup S^{-}}$

その後、K. Lang は、およびについての仮定を一切使用しない TB アルゴリズムの拡張である Traxbar アルゴリズムを提案した。[ ^{21 ]しかし}、 Traxbar では、構築された DFA の最小性が保証されない。EM Gold も、その研究 [19] で^、最小DFA識別のためのヒューリスティック アルゴリズムを提案した。Gold のアルゴリズムでは、およびが正規言語の特性セットを含んでいると仮定する。そうでない場合、構築された DFA は、またはと矛盾する。その他の注目すべき DFA 識別アルゴリズムには、RPNI アルゴリズム^{[ 22 ]}、Blue-Fringe 証拠駆動型状態マージ アルゴリズム^{[ 23 ] 、および Windowed-EDSM [ 24 ]}がある 。もう 1 つの研究方向は、進化的アルゴリズム の応用である。スマート状態ラベリング 進化的アルゴリズム^{[ 25 ]} ${\displaystyle S^{+}}$ ${\displaystyle S^{-}}$ ${\displaystyle S^{+}}$ ${\displaystyle S^{-}}$ ${\displaystyle S^{+}}$ ${\displaystyle S^{-}}$ ${\displaystyle S^{+}}$ ${\displaystyle S^{-}}$

さらにもう一つ前進したのは、 Marjin JH Heuleと S. Verwer によるSATソルバーの応用である。最小 DFA 識別問題は、ブール式の充足可能性の決定に縮減される。^{[ 26 ]}主なアイデアは、入力セットに基づいて拡張プレフィックスツリーアクセプタ（対応するラベルを持つすべての入力単語を含むトライ）を構築し、状態を持つ DFA を見つける問題を、ある色の頂点が 1 つの状態にマージされるときに、生成されたオートマトンが決定論的であり、およびに準拠するような方法でツリーの頂点を状態によって色付けすることに縮減する。このアプローチでは最小の DFA を見つけることはできるが、入力データのサイズが増加すると実行時間が指数関数的に増加する。そのため、Heule と Verwer の最初のアルゴリズムは、後に SAT ソルバーの実行前に EDSM アルゴリズムのいくつかのステップを実行するように拡張され、DFASAT アルゴリズムとなった。^{[ 27 ]} これにより問題の探索空間を縮小できるが、最小性保証は失われる。探索空間を縮小する別の方法がUlyantsevらによって提案されている^{[ 28 ]} 。これは幅優先探索アルゴリズムに基づく新しい対称性破壊述語を用いるもので、探索対象のDFAの状態は、初期状態から開始されるBFSアルゴリズムに従って番号付けされるように制約される。このアプローチは、同型オートマトンを排除することで探索空間を縮小する。 ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle S^{+}}$ ${\displaystyle S^{-}}$ ${\displaystyle C!}$

同等のモデル

読み取り専用の右向きチューリングマシン

読み取り専用右向きチューリングマシンは、右方向にのみ移動する特殊なタイプのチューリングマシンであり、DFAとほぼ同等である。^{[ 29 ]} 単一無限テープに基づく定義は、7組の

${\displaystyle M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},F\rangle ,}$

どこ

${\displaystyle Q}$は有限の状態集合である。

${\displaystyle \Gamma }$テープアルファベット/シンボルの有限集合です。

${\displaystyle b\in \Gamma }$空白のシンボルです（計算中のどのステップでもテープ上で無限に出現することが許される唯一のシンボルです）。

${\displaystyle \Sigma }$は、 bを含まないのサブセットであり、入力シンボルの集合です。 ${\displaystyle \Gamma }$

${\displaystyle \delta :Q\times \Gamma \to Q\times \Gamma \times \{R\}}$は遷移関数と呼ばれる関数で、Rは右への移動（右シフト）です。

${\displaystyle q_{0}\in Q}$初期状態です。

${\displaystyle F\subseteq Q}$最終状態または受け入れ状態の集合です。

マシンは常に正規言語を受け入れます。言語が空でなくなるためには、 集合F（HALT状態）の要素が少なくとも1つ存在する必要があります。

3状態、2シンボルの読み取り専用チューリングマシンの例

	現在の状態A			現在の状態B			現在の状態C
テープ記号	記号を書く	テープを移動する	次の州	記号を書く	テープを移動する	次の州	記号を書く	テープを移動する	次の州
0	1	R	B	1	R	あ	1	R	B
1	1	R	C	1	R	B	1	北	停止

${\displaystyle Q=\{A,B,C,{\text{HALT}}\};}$

${\displaystyle \Gamma =\{0,1\};}$

${\displaystyle b=0}$、 "空白";

${\displaystyle \Sigma =\varnothing }$、空集合。

${\displaystyle \delta =}$上記の状態表を参照してください。

${\displaystyle q_{0}=A}$、初期状態;

${\displaystyle F=}$最終状態の 1 つの要素セット: 。 ${\displaystyle \{{\text{HALT}}\}}$

参照

• 決定性非巡回有限状態オートマトン
• DFA最小化
• モナド二階論理
• パワーセット構造
• 量子有限オートマトン
• 単語の分離問題
• チューリングマシン
• 双方向有限オートマトン
• 重み付きオートマトン

注記

1. ホップクロフト、モトワニ、ウルマン 2006 .
2. マカロック＆ピッツ 1943年。
3. ラビン＆スコット 1959 .
4. Bai, Gina R.; Clee, Brian; Shrestha, Nischal; Chapman, Carl; Wright, Cimone; Stolee, Kathryn T. (2019). 「正規表現合成タスクで使用されるツールと戦略の探求」 . Guéhéneuc, Yann-Gaël; Khomh, Foutse; Sarro, Federica (編). Proceedings of the 27th International Conference on Program Comprehension, ICPC 2019, Montreal, QC, Canada, May 25-31, 2019 . IEEE / ACM. pp.  197– 208. doi : 10.1109/ICPC.2019.00039 . ISBN 978-1-7281-1519-1。
5. Mogensen, Torben Ægidius (2011). 「字句解析」.コンパイラ設計入門. 大学におけるコンピュータサイエンスのトピック. ロンドン: Springer. p. 12. doi : 10.1007/978-0-85729-829-4_1 . ISBN 978-0-85729-828-7。
6. ローソン 2004、129ページ。
7. サカロヴィッチ 2009、228ページ。
8. ローソン 2004、128ページ。
9. Grusho, AA (1973). 「ランダムオートマトングラフの特定の特性の極限分布」.ソ連科学アカデミー数学ノート. 4 : 633–637 . doi : 10.1007/BF01095785 . S2CID 121723743 . 
10. Cai, Xing Shi; Devroye, Luc (2017年10月). 「ランダムに選択された決定性オートマトン（deterministic automaton）のグラフ構造」. Random Structures & Algorithms . 51 (3): 428– 458. arXiv : 1504.06238 . doi : 10.1002/rsa.20707 . S2CID 13013344 . 
11. Carayol, Arnaud; Nicaud, Cyril (2012年2月).ランダム決定性オートマトンにおけるアクセス可能な状態数の分布. STACS'12 (第29回コンピュータサイエンスの理論的側面に関するシンポジウム). 第14巻. パリ, フランス. pp.  194– 205.
12. ホップクロフト＆ウルマン 1979年、59～60頁。
13. Rose, Gene F. (1968). 「言語族における有限性を保持する閉包」. Journal of Computer and System Sciences . 2 (2): 148– 168. doi : 10.1016/S0022-0000(68)80029-7 .
14. Spanier, E. (1969). 「文法と言語」. American Mathematical Monthly . 76 ( 4): 335– 342. doi : 10.1080/00029890.1969.12000214 . JSTOR 2316423. MR 0241205 .  
15. サカロヴィッチ 2009、105ページ。
16. ローソン 2004、63ページ。
17. Esparza Estaun, Francisco Javier; Sickert, Salomon; Blondin, Michael (2016年11月16日). 「集合に対する演算とテスト：DFAへの実装」(PDF) . Automata and Formal Languages 2017/18 . 2018年8月8日時点のオリジナル(PDF)からのアーカイブ。
18. ローソン 2004、46ページ。
19. Gold, EM (1978). 「与えられたデータからのオートマトン識別の複雑性」.情報制御. 37 (3): 302– 320. doi : 10.1016/S0019-9958(78)90562-4 .
20. De Vries, A. (2014年6月28日).有限オートマトン：動作と合成. エルゼビア. ISBN 9781483297293。
21. Lang, Kevin J. (1992). 「ランダムDFAはスパースな一様分布の例から近似的に学習できる」.第5回計算学習理論ワークショップ - COLT '92 の議事録. pp.  45– 52. doi : 10.1145/130385.130390 . ISBN 089791497X. S2CID  7480497 .
22. Oncina, J.; García, P. (1992). 「多項式更新時間による正規言語の推論」.パターン認識と画像解析. 機械知覚と人工知能シリーズ. 第1巻. pp.  49– 61. doi : 10.1142/9789812797902_0004 . ISBN 978-981-02-0881-3。
23. Lang, Kevin J.; Pearlmutter, Barak A.; Price, Rodney A. (1998). 「Abbadingo one DFA学習コンペティションの結果と新しい証拠駆動型状態マージアルゴリズム」.文法推論(PDF) . コンピュータサイエンス講義ノート. 第1433巻. pp.  1– 12. doi : 10.1007/BFb0054059 . ISBN 978-3-540-64776-8。
24. Adriaans, Pieter; Fernau, Henning; Zaanen, Menno van (2002年9月23日). Beyond EDSM | Proceedings of the 6th International Colloquium on Grammatical Inference: Algorithms and Applications . Springer. pp.  37– 48. ISBN 9783540442394。
25. Lucas, SM; Reynolds, TJ (2005). 「スマートな状態ラベル付け進化アルゴリズムを用いた決定論的有限オートマトン学習」. IEEE Transactions on Pattern Analysis and Machine Intelligence . 27 ( 7): 1063– 1074. doi : 10.1109/TPAMI.2005.143 . PMID 16013754. S2CID 14062047 .  
26. Heule, MJH (2010). 「SATソルバーを用いた正確なDFA同定」.文法推論：理論的結果と応用. 文法推論：理論的結果と応用. ICGI 2010. コンピュータサイエンス講義ノート. コンピュータサイエンス講義ノート. 第6339巻. pp.  66– 79. doi : 10.1007/978-3-642-15488-1_7 . ISBN 978-3-642-15487-4。
27. Heule, Marijn JH ; Verwer, Sicco (2013). 「満足度ソルバーを用いたソフトウェアモデル合成」経験的ソフトウェア工学. 18 (4): 825– 856. doi : 10.1007/s10664-012-9222-z . hdl : 2066/103766 . S2CID 17865020 . 
28. Ulyantsev, Vladimir; Zakirzyanov, Ilya; Shalyto, Anatoly (2015). 「DFA識別のためのBFSベースの対称性破壊述語」.言語とオートマトン理論と応用. コンピュータサイエンス講義ノート. 第8977巻. pp.  611– 622. doi : 10.1007/978-3-319-15579-1_48 . ISBN 978-3-319-15578-4。
29. デイビス、マーティン、ロン・シーガル、エレイン・J・ワイユカー (1994). 『計算可能性、複雑性、言語と論理：理論計算機科学の基礎』（第2版）サンディエゴ：アカデミック・プレス、ハーコート・ブレース・アンド・カンパニー. ISBN 0-12-206382-1。

参考文献

• ホップクロフト, ジョン・E.; ウルマン, ジェフリー・D. (1979). 『オートマトン理論、言語、計算入門』（第1版）. アディソン・ウェスレー. ISBN 0-201-02988-X。（印刷障害のある利用者もアクセス可能）
• ホップクロフト, ジョン・E. ;モトワニ, ラジーヴ;ウルマン, ジェフリー・D. (2006) [1979].オートマトン理論、言語、計算入門（第3版）. アディソン・ウェスレー. ISBN 0-321-45536-3。
• ローソン、マーク・V. (2004).有限オートマトン. チャップマン・アンド・ホール/CRC. ISBN 1-58488-255-7. Zbl  1086.68074 .
• McCulloch, WS; Pitts, W. (1943). 「神経活動に内在する観念の論理的計算」.数理生物物理学紀要. 5 (4): 115– 133. doi : 10.1007/BF02478259 . PMID  2185863 .
• ラビン, MO; スコット, D. (1959). 「有限オートマトンとその決定問題」 . IBM J. Res. Dev . 3 (2): 114– 125. doi : 10.1147/rd.32.0114 .
• サカロヴィッチ、ジャック（2009年）『オートマトン理論の要素』 フランス語からの翻訳：ルーベン・トーマス。ケンブリッジ：ケンブリッジ大学出版局。ISBN 978-0-521-84425-3. Zbl  1188.68177 .

さらに読む

• シプサー、マイケル(1997).計算理論入門（第1版）. PWS Publishing. ISBN 978-0-534-94728-6。（印刷障害のある利用者も閲覧可能） — 1.1 : 「有限オートマトン」31～47ページ。4.1 :「決定可能言語 - 正規言語に関する決定可能問題」152～155ページ。4.4 : DFAは正規言語のみを受け付けます

「 https://en.wikipedia.org/w/index.php?title=決定論的有限オートマトン&oldid =1285525393」より取得