決定性有限オートマトンのソースを表示

'''決定性有限オートマトン'''（けっていせいゆうげんオートマトン、{{lang-en-short|Deterministic Finite Automaton}}）または'''決定性有限状態機械'''（けっていせいゆうげんじょうたいきかい、{{lang-en-short|Deterministic Finite State Machine}}）は、状態と入力によって次に遷移すべき状態が一意に定まる[[有限オートマトン]]である。'''DFA''' と略記される。

DFAは入力文字列を受け付ける。各入力文字について、遷移関数にしたがって新たな状態に遷移する。最後に入力文字を受け付けたとき、受理状態であれば入力文字列は受理された、そうでなければ入力文字列は拒否されたと判断される。

[[非決定性有限オートマトン]]は、決定性有限オートマトンと同じように正規集合を認識でき、必ず決定性オートマトンに変換できる<ref>コンパイラI 原理・技法・ツール、A.V.エイホ・R.セシィ、J.D.ウルマン 共著、原田賢一 訳、サイエンス社、134頁</ref>。

==形式的定義==
DFA とは5組  ''A'' = (''Q'', &Sigma;, &delta;, ''q''<sub>0</sub>, ''F'') のうち以下の性質（右側）を満たすものをいう。それぞれの要素は以下（左側）のように呼ばれる{{sfn|Hopcroft et al.|2001|p=46}}。
* 状態集合 (''Q'' : [[有限集合]])
* 文字集合 (&Sigma; : 有限集合)
* 遷移関数 (&delta; : ''Q'' &times; &Sigma; &rarr; ''Q'')
* 開始状態 (''q''<sub>0</sub> &isin; ''Q'')
* 受理状態の集合 (''F'' &sube; ''Q'')

いま ''a = a<sub>0</sub>a<sub>1</sub> ... a<sub>n&minus;1</sub>'' という文字集合 &Sigma; に含まれる文字から構成される文字列が与えられたとする。各 ''i'' = ''0, &hellip;, n&minus;1'' について帰納的に  
: ''q<sub>i+1</sub>'' := &delta;(''q<sub>i</sub>'', ''a<sub>i</sub>'') 
とおく。 ''q<sub>n</sub>'' &isin; ''F'' が成り立つとき、 ''A'' は文字列 ''a'' を'''受理する'''と言う。状態の列 ''q''<sub>i</sub> は文字列 ''a'' が与えられたとき、遷移関数 ''&delta;'' にしたがってこのマシンが状態遷移を繰り返すことを示している。[[形式言語|言語]]の中でこのマシンが受容する文字列の集合が、このDFAの理解する言語である。

== 例 ==
以下は DFA である ''A'' の例であり、入力文字としては 0 と 1 を受け付けて、0の個数が偶数である入力文字列のみを受理する。

''A'' = (''Q'', &Sigma;, &delta;, ''q''<sub>0</sub>, ''F'') であるとき
*''Q'' = {''q''<sub>0</sub>, ''q''<sub>1</sub>},
*&Sigma; = {0, 1},
*''F'' = {''q''<sub>0</sub>}, 
*&delta; は以下の[[状態遷移表]]で定義される。
{| class="wikitable" style="margin:0 auto; text-align:center; width:50%"
|+遷移関数 &delta; の状態遷移表
! !! 0 !! 1
|-
! ''q''<sub>0</sub>
| ''q''<sub>1</sub> || ''q''<sub>0</sub>
|-
! ''q''<sub>1</sub>
| ''q''<sub>0</sub> || ''q''<sub>1</sub>
|}
''A'' の[[状態遷移図]]は以下の通りである。

:[[Image:Even Number of Zeros DFA.png|center|''A'' の状態遷移図]]

状態 ''q''<sub>0</sub> にあるとき、それまでの入力文字列に偶数個の 0 が含まれていたことを意味し、状態 ''q''<sub>1</sub> にあるときは奇数個であることを意味する。1 が入力されたとき、このオートマトンの状態は変化しない。入力が終了したときの状態を見れば、入力文字列に偶数個の 0 が含まれていたか否かがわかる。

''A''の言語は以下の[[正規表現]]で記述される[[正規言語]]である。
<!-- The \,\! is to keep the formula rendered as PNG instead of HTML to ensure consistency of representation. Please don't remove it.-->

:<math>1^*(01^*01^*)^* \,\!</math>

== 非輪状決定性有限オートマトン ==
'''非輪状決定性有限オートマトン'''（ひりんじょうけっていせいゆうげんオートマトン、{{lang-en-short|Acyclic Deterministic Finite Automaton}}）は輪状（環状）の遷移の連鎖がない決定性有限オートマトンである。ADFA と略記される。換言すれば、このオートマトンでは有限の文字列集合しか表現できない。これは非常に高速な検索が可能な単語格納データ構造として使用される。最小化したADFAは非常にコンパクトになり、そのサイズは格納されるキーの数には比例しない。実際、ある閾値を越えると、格納する単語を増やしたときにデータ構造のサイズは減少しはじめる。その閾値サイズは格納される文字列がどれだけ複雑であるかに依存する。[[トライ木]]は一種のADFAである。

== 脚注　==
{{reflist}}

== 参考文献　==
* {{cite book
|last1       = Hopcroft
|first1      = John E
|last2       = Ullman
|first2       = Jeffrey D.
|last3       =Motwani
|first3       = Rajeev
|year        = 2001
|title          = Introduction to automata theory, languages, and computation
|edition     = 2nd 
|url            = http://www.pmfst.unist.hr/~milica/Matem_teorija_r/MTR_web/Introduction%20To%20Automata%20Theory.pdf
|format      = PDF
|publisher  = Addison-Wesley
|isbn         = 0-201-44124-1
|ref            = {{sfnref|Hopcroft et al.|2001}}
}}

== 関連項目 ==
* [[トライ木]]
* [[非決定性有限オートマトン]]
* [[チューリングマシン]]

{{DEFAULTSORT:けつていせいゆうけんおとまとん}}
[[Category:有限オートマトン]]
[[Category:計算モデル]]
[[Category:数学に関する記事]]