決定性有限オートマトン

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

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

決定性有限オートマトン(DFA)

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

DFAの正式な定義

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

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

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

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

  • q0任意の入力が処理されるから初期状態である(Q 0 ∈Q)。

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

DFAのグラフィック表現

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

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

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

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

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

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

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