決定論的有限オートマトン

理論計算機科学の一分野である計算理論において、決定性有限オートマトン( DFA ) は、決定性有限アクセプタ( DFA )、決定性有限状態機械( DFSM )、または決定性有限状態オートマトン( DFSA )とも呼ばれ、文字列によって一意に決定される状態シーケンスを実行することにより、指定された文字列を受け入れるか拒否する有限状態機械です。 ^[1]決定性とは、計算実行の一意性を指します。有限状態機械を捉える最も単純なモデルを求めて、ウォーレン・マカロックとウォルター・ピッツは、 1943 年に有限オートマトンに似た概念を導入した最初の研究者の 1 人でした。 ^{[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、Σ、δ、q0 _、F）で構成され、

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

w = a ₁ a ₂ ... a _{n を}アルファベットΣ上の文字列とします。オートマトンM は、次の条件でQに状態のシーケンスr ₀、r ₁、 ...、r _{n が}存在する場合、文字列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の最後の入力によってマシンが受け入れ状態の 1 つで停止した場合、マシンはw を受け入れることを意味します。それ以外の場合、オートマトンが文字列を拒否すると言われます。Mが受け入れる文字列の集合は、Mによって認識される言語であり、この言語はL ( M )で表されます。

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

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

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

M = ( Q , Σ, δ , q ₀ , F )ただし

• Q = { S1、S2 _}​
• Σ = {0, 1}
• q ₀ = S ₁
• F = { S ₁ }であり、
• δ は次の状態遷移表によって定義されます。

状態S ₁は、これまでの入力に 0 が偶数個あったことを表します。一方、状態S _{2 は}奇数個であることを示します。入力に 1 があっても、オートマトンの状態は変わりません。入力が終了すると、状態は入力に 0 が偶数個含まれていたかどうかを示します。入力に 0 が偶数個含まれていた場合、M は受け入れ状態である状態S ₁で終了し、入力文字列は受け入れられます。

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

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

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

ローカルオートマトンとは、必ずしも完全ではないDFAであり、同じラベルを持つすべての辺が1つの頂点につながる。ローカルオートマトンでは、単語の言語内におけるメンバーシップが単語の長さ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]

DFA が、DFA が認識可能な言語に操作を適用して得られる言語を認識する場合、DFA はその操作 に対して閉じていると言われます。DFA は次の操作に対して閉じています。

各操作について、状態数に関する最適な構成は、状態複雑度の研究で決定されています。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 をシミュレートするための単純な線形時間、定数空間、オンライン アルゴリズムがあるため、最も実用的な計算モデルの 1 つです。また、次のことを認識して 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 も認識できない単純な言語の典型的な例は、括弧またはDyck 言語、つまり単語「(()())」のように適切に対になった括弧で構成される言語です。直感的に、DFA は Dyck 言語を認識できません。これは、DFA がカウントできないためです。DFA のようなオートマトンには、現在開いている括弧の可能な数を表す状態が必要であり、これは無制限の数の状態が必要になることを意味します。もう 1 つのより単純な例は、有限だが任意の数のaとそれに続く同数の bの形式a ⁿ b ⁿの文字列で構成される言語です。^[18]

肯定的な単語の集合と否定的な単語の集合が与えられれば、 のすべての単語を受け入れ、 のすべての単語を拒否する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]があります。別の研究方向は、}進化的アルゴリズム の応用です。スマート状態ラベリング進化的アルゴリズム^[25]は、トレーニング データ (セットおよび)に、一部の単語が間違ったクラスに割り当てられるという意味で ノイズが含まれる、修正された DFA 識別問題を解決${\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 つ存在する必要があります。

${\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}}\}}$

• ホップクロフト、ジョン E.、ウルマン、ジェフリー D. (1979)。オートマトン理論、言語、計算入門(第 1 版)。アディソン ウェスレー。ISBN 0-201-02988-X。（印刷障害のある利用者も利用可能）
• ホップクロフト、ジョン E. ;モトワニ、ラジーブ;ウルマン、ジェフリー D. (2006) [1979].オートマトン理論、言語、計算入門(第 3 版). Addison-Wesley. ISBN 0-321-45536-3。
• ローソン、マーク V. (2004)。有限オートマトン。チャップマン＆ホール/CRC。ISBN 1-58488-255-7.ZBL1086.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.ZBL1188.68177  。​

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