|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 決 ： [けつ] 【名詞】 1. decision 2. vote ・ 定性 ： [ていせい] 【名詞】 1. qualitative 2. stability of a substance ・ 有 ： [う, ゆう] 1. (n,vs) possession ・ 有限 ： [ゆうげん] 1. (adj-na,n) finite 2. limited ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana) ・ マトン ： [まとん] (n) mutton, (n) mutton
決定性有限オートマトン（けっていせいゆうげんオートマトン、）または決定性有限状態機械（けっていせいゆうげんじょうたいきかい、）は、状態と入力によって次に遷移すべき状態が一意に定まる有限オートマトンである。DFA と略記される。 DFAは入力文字列を受け付ける。各入力文字について、遷移関数にしたがって新たな状態に遷移する。最後に入力文字を受け付けたとき、受理状態であれば入力文字列は受理された、そうでなければ入力文字列は拒否されたと判断される。 非決定性有限オートマトンは、決定性有限オートマトンと同じように正規集合を認識でき、必ず決定性オートマトンに変換できる〔コンパイラI 原理・技法・ツール、A.V.エイホ・R.セシィ、J.D.ウルマン 共著、原田賢一 訳、サイエンス社、134頁〕。 ==形式的定義== DFA とは5組 ''A'' = (''Q'', Σ, δ, ''q''0, ''F'') のうち以下の性質（右側）を満たすものをいう。それぞれの要素は以下（左側）のように呼ばれる。 * 状態集合 (''Q'' : 有限集合) * 文字集合 (Σ : 有限集合) * 遷移関数 (δ : ''Q'' × Σ → ''Q'') * 開始状態 (''q''0 ∈ ''Q'') * 受理状態の集合 (''F'' ⊆ ''Q'') いま ''a = a0a1 ... an−1'' という文字集合 Σ に含まれる文字から構成される文字列が与えられたとする。各 ''i'' = ''0, …, n−1'' について帰納的に : ''qi+1'' := δ(''qi'', ''ai'') とおく。 ''qn'' ∈ ''F'' が成り立つとき、 ''A'' は文字列 ''a'' を受理すると言う。状態の列 ''q''i は文字列 ''a'' が与えられたとき、遷移関数 ''δ'' にしたがってこのマシンが状態遷移を繰り返すことを示している。言語の中でこのマシンが受容する文字列の集合が、このDFAの理解する言語である。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「決定性有限オートマトン」の詳細全文を読む スポンサード リンク
|