決定性有限オートマトン

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

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

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

DFAでは、入力シンボルごとに、マシンが移動する状態を決定できます。したがって、それは呼ばれますDeterministic Automaton。状態の数が有限であるため、マシンはと呼ばれますDeterministic Finite Machine または Deterministic Finite Automaton.

DFAの正式な定義

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

• Q は有限の状態のセットです。

• ∑ アルファベットと呼ばれる記号の有限集合です。

• δ は遷移関数です。ここで、δ：Q×∑→Q

• q₀任意の入力が処理されるから初期状態である（Q ₀ ∈Q）。

• F Qの最終状態/状態のセットです（F⊆Q）。

DFAのグラフィック表現

DFAは、次の有向グラフで表されます。 state diagram。

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

例

決定性有限オートマトンを→

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

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

現状	入力0の次の状態	入力1の次の状態
a	a	b
b	c	a
c	b	c

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