Automata-theory-deterministic-finite-automaton

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

有限オートマトンは2つのタイプに分類することができます-

• 決定論的有限オートマトン（DFA）
• 非決定性有限オートマトン（NDFA/NFA）

決定論的有限オートマトン（DFA）

DFAでは、入力シンボルごとに、マシンが移動する状態を決定できます。 したがって、*決定的オートマトン*と呼ばれます。 状態の数が有限であるため、マシンは*確定的有限マシン*または*確定的有限オートマトン*と呼ばれます。

DFAの正式な定義

DFAは5タプル（Q、∑、δ、q〜0〜、F）で表すことができます。

• Q は有限状態のセットです。
• ∑ は、アルファベットと呼ばれる有限の記号セットです。
• *δ*は遷移関数です。δ：Q×∑→Q
• * q〜0〜*は、入力が処理される初期状態です（q〜0〜∈Q）。
• F は、Qの最終状態の状態です（F⊆Q）。

DFAのグラフィカル表現

DFAは、*状態図*と呼ばれる有向グラフで表されます。

• 頂点は状態を表します。
• 入力アルファベットのラベルが付いた弧は、遷移を示します。
• 初期状態は、空の単一の着信アークによって示されます。
• 最終状態は二重丸で示されます。

例

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

• Q = \ {a、b、c}、
• ∑ = \ {0、1}、
• q〜0〜= \ {a}、
• F = \ {c}、および

次の表に示す遷移関数δ-

Present State	Next State for Input 0	Next State for Input 1
a	a	b
b	c	a
c	b	c

そのグラフィカルな表現は次のようになります-

DFAグラフィカル表現