Loading article…
理論計算機科学の一分野である計算理論において、決定性有限オートマトン（DFA）は、決定性有限アクセプタ（DFA）、決定性有限状態機械（DFSM）、または決定性有限状態オートマトン（DFSA）とも呼ばれ、与えられた記号列を、その記号列によって一意に決定される状態シーケンスを実行することによって受理または拒否する有限状態機械である。 [ 1 ]決定性とは、計算実行の一意性を指す。有限状態機械を捉える最も単純なモデルを探求する中で、ウォーレン・マカロックとウォルター・ピッツは、 1943年に有限オートマトンに似た概念を導入した最初の研究者の一人であった。[ 2 ] [ 3 ]
図は、状態図を用いた決定性有限オートマトンを示しています。この例のオートマトンには、S 0、S 1、S 2の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 0 , F )である。
w = a 1 a 2 ... a n をアルファベットΣ上の文字列とする。オートマトンM は、 Q内に以下の条件を満たす状態のシーケンスr 0 , r 1 , ..., r nが存在する場合に、文字列w を受理する。
言葉で説明すると、最初の条件は、機械が開始状態q 0から始まることを示しています。2番目の条件は、文字列wの各文字が与えられたとき、機械は遷移関数δに従って状態から状態へと遷移することを示しています。最後の条件は、wの最後の入力によって機械が受理状態のいずれかで停止する場合、機械はw を受理することを示しています。そうでない場合、オートマトンはその文字列を拒否すると言われます。Mが受理する文字列の集合は、 Mによって認識される言語であり、この言語はL ( M )で表されます。
受理状態も開始状態も持たない決定性有限オートマトンを遷移システムまたは半オートマトンと呼ぶ。
形式的な定義についてより包括的に知りたい場合は、オートマトン理論を参照してください。
以下の例は、バイナリアルファベットを持つDFA Mで、入力には偶数個の0が含まれている必要があります。
M = ( Q , Σ, δ , q 0 , F )ここで
状態S1は、入力に偶数個の0が含まれていることを示し、S2は奇数個であることを示します。入力に1が含まれていても、オートマトンの状態は変化しません。入力が終了すると、入力に偶数個の0が含まれていたかどうかが状態によって示されます。入力に偶数個の0が含まれていた場合、Mは受理状態である状態S1で終了するため、入力文字列は受理されます。
Mによって認識される言語は、正規表現で与えられる正規言語です。ここで はクリーネスターであり、たとえば は連続する任意の数 (場合によってはゼロ) の 1 を表します。(1*) (0 (1*) 0 (1*))**1*
上記の定義によれば、決定性有限オートマトンは常に完全である。つまり、各状態から各入力記号への遷移を定義する。
これは最も一般的な定義ですが、一部の著者は、決定性有限オートマトンという用語を少し異なる概念に使用しています。それは、各状態と各入力記号に対して最大で1 つの遷移を定義するオートマトンであり、遷移関数は部分的であっても構いません。[ 5 ]遷移が定義されていない場合、このようなオートマトンが停止します。
ローカルオートマトンとは、必ずしも完全ではないDFAであり、同じラベルを持つすべてのエッジが単一の頂点につながるものです。ローカルオートマトンは、ローカル言語のクラスを受け入れます。ローカル言語とは、単語が言語に属するかどうかが、その単語上の長さ2の「スライディングウィンドウ」によって決定される言語です。[ 6 ] [ 7 ]
アルファベットA上のMyhillグラフは、頂点集合Aと、「開始」および「終了」とラベル付けされた頂点の部分集合を持つ有向グラフです。Myhill グラフが受理する言語は、開始頂点から終了頂点への有向パスの集合です。したがって、このグラフはオートマトンとして機能します。[ 6 ] Myhill グラフが受理する言語のクラスは、ローカル言語のクラスです。[ 8 ]
開始状態と受理状態を無視すると、n個の状態とk個のアルファベットを持つDFA は、すべての頂点が1、...、kとラベル付けされたk 個の出力弧を持つn個の頂点の有向グラフ( k出力有向グラフ) と見なすことができます。k ≥ 2が固定整数である場合、このようなk出力有向グラフで一様にランダムに選択された最大の強連結成分(SCC)は高い確率で線形サイズであり、すべての頂点から到達可能であることが知られています。 [ 9 ]また、 n の増加に伴ってk が増加することが許される場合、有向グラフ全体が、連結性に関するErdős–Rényi モデルと同様の強連結性に関する相転移を起こすことも証明されています。[ 10 ]
ランダムDFAでは、1つの頂点から到達可能な頂点の最大数は、高い確率で最大のSCCの頂点数に非常に近い。 [ 9 ] [ 11 ]これは、最小入次数が1の最大の誘導部分有向グラフにも当てはまり、これは1-コアの有向バージョンと見なすことができる。[ 10 ]
DFAが、DFAが認識可能な言語に演算を適用して得られる言語を認識する場合、DFAはその演算に関して閉じていると言われます。DFAは以下の演算に関して閉じています。
各操作について、状態数に関して最適な構成が状態複雑性研究で決定されている。DFAは非決定性有限オートマトン（NFA）と等価であるため、これらの閉包はNFAの閉包特性を用いて証明することもできる。
与えられたDFAの実行は、遷移関数の非常に一般的な定式化とそれ自身との合成のシーケンスとして見なすことができる。ここでは、その関数を構築する。
特定の入力シンボルに対して遷移関数を構築することができる定義することによってすべての人々のために（この技はカレー風味付けと呼ばれる。）この観点からすると、Q内の状態に「作用」して別の状態を生成する。次に、さまざまな関数に繰り返し適用される関数合成の結果を検討することができる。、など。2つの文字が与えられた場合新しい関数を定義することができる、 どこ関数合成を表します。
明らかに、このプロセスは再帰的に継続することができ、次の再帰的な定義が得られます。:
すべての単語に対して定義されていますDFA の実行は、次の合成のシーケンスです。それ自体と。
関数の合成を繰り返すとモノイドが形成されます。遷移関数の場合、このモノイドは遷移モノイド、または変換半群として知られています。この構成は逆方向にも実行できます。再構築できるしたがって、この2つの記述は同等である。
DFAは、入力ストリーム上でDFAをシミュレートするための、単純な線形時間、定数空間、オンラインアルゴリズムが存在するため、最も実用的な計算モデルの一つです。また、次のようなDFAを認識する効率的なアルゴリズムも存在します。
DFAは標準形（最小DFA ）に還元できるため、以下のものを決定するための効率的なアルゴリズムも存在します。
DFA は、計算能力において非決定性有限オートマトン(NFA)と同等です。これは、まず、任意の DFA は NFA でもあるため、NFA は DFA ができることを実行できるからです。また、NFA が与えられた場合、べき集合構成を使用して、 NFA と同じ言語を認識する DFA を構築できますが、DFA の状態数は NFA よりも指数関数的に大きくなる可能性があります。[ 15 ] [ 16 ]ただし、NFA は DFA と計算的に同等ですが、上記の問題は必ずしも NFA に対しても効率的に解決されるとは限りません。NFA の非普遍性問題は、指数関数的に小さいサイズの拒否語を持つ小さな NFA が存在するため、 PSPACE 完全です。DFA は、すべての状態が最終状態である場合に限り普遍的ですが、これは NFA には当てはまりません。等価性、包含性、最小化問題も、NFA の補集合を形成する必要があり、その結果、サイズが指数関数的に爆発するため、PSPACE 完全です。[ 17 ]
一方、有限状態オートマトンが認識できる言語には厳密に制限があります。定数以上の空間を必要とする問題を含む多くの単純な言語は、DFA では認識できません。DFA では認識できない単純な記述言語の典型的な例は、括弧またはDyck 言語、つまり単語 "(()())" のように適切にペアになった括弧で構成される言語です。直感的に言えば、DFA はカウントできないため、DFA では Dyck 言語を認識できません。DFA のようなオートマトンには、任意の数の「現在開いている」括弧を表す状態が必要であり、つまり無制限の数の状態が必要になります。もう 1 つのより単純な例は、有限だが任意の数のaと、それに続く同数のbからなる形式の文字列a n b nで構成される言語です。[ 18 ]
肯定的な単語のセットが与えられたそして否定的な言葉のセットからのすべての単語を受け入れるDFAを構築できますそしてすべての単語を拒否しますこの問題はDFA識別（合成、学習）と呼ばれます。一部のDFAは線形時間で構築できますが、最小状態数のDFAを識別する問題はNP完全です。[ 19 ] 最小DFA識別のための最初のアルゴリズムはTrakhtenbrotとBarzdinによって提案され[ 20 ] 、 TBアルゴリズムと呼ばれています。しかし、TBアルゴリズムは、すべての単語が所定の長さまでのいずれかに含まれる。
その後、K. Langは、TBアルゴリズムの拡張版を提案したが、これは、そしてTraxbarアルゴリズム[ 21 ]。 しかし、Traxbarは構築されたDFAの最小性を保証しません。EM Goldは、彼の研究[ 19 ]で最小DFA識別のためのヒューリスティックアルゴリズムも提案しました。Goldのアルゴリズムは、そして正規言語の特性セットが含まれている必要があります。そうでない場合、構築された DFA は以下と矛盾します。またはその他の注目すべき DFA 識別アルゴリズムには、RPNI アルゴリズム[ 22 ] 、 Blue-Fringe 証拠駆動型状態マージアルゴリズム[ 23 ] 、Windowed-EDSM [ 24 ]などがあります。もう 1 つの研究方向は、進化アルゴリズム の適用です。スマート状態ラベル付け進化アルゴリズム[ 25 ]は、トレーニング データ (セットそして）は、一部の単語が間違ったクラスに割り当てられているという意味でノイズが多い。
さらに、 Marjin JH HeuleとS. VerwerによるSATソルバーの応用により、DFAの最小識別問題がブール式の充足可能性の判定に帰着するという新たな進歩がもたらされた。[ 26 ]主なアイデアは、入力セットに基づいて拡張プレフィックスツリーアクセプタ（対応するラベルを持つすべての入力単語を含むトライ）を構築し、DFAを見つける問題を、木の頂点を色付けする状態1つの色の頂点が1つの状態にマージされたときに、生成されたオートマトンが決定論的であり、そしてこのアプローチでは最小のDFAを見つけることができますが、入力データのサイズが増加すると実行時間が指数関数的に増加するという問題があります。そのため、HeuleとVerwerの初期アルゴリズムは、SATソルバーの実行前にEDSMアルゴリズムのいくつかのステップを実行するように後に拡張され、DFASATアルゴリズムとなりました。[ 27 ] これにより問題の探索空間を縮小できますが、最小性の保証が失われます。探索空間を縮小する別の方法は、Ulyantsevら[ 28 ]によって、幅優先探索アルゴリズムに基づく新しい対称性破壊述語によって提案されています。つまり、探しているDFAの状態は、初期状態から開始されたBFSアルゴリズムに従って番号付けされるように制約されます。このアプローチにより、探索空間は同型オートマトンを排除することによって。
読み取り専用の右移動チューリングマシンは、右方向にのみ移動する特殊なタイプのチューリングマシンであり、DFAとほぼ完全に同等である。[ 29 ] 単一の無限テープに基づく定義は7タプルである。
どこ
この機械は常に正規言語を受け入れます。言語が空でないためには、集合F（HALT状態）の要素が少なくとも1つ存在する必要があります。
