[Python] 決定性有限オートマトン

決定性有限オートマトンを使った文字列検索のアルゴリズムを書くために、決定性有限オートマトンについてまずは考えます。

決定性有限オートマトン（けっていせいゆうげんオートマトン、英: Deterministic Finite Automaton）または決定性有限状態機械（けっていせいゆうげんじょうたいきかい、英: Deterministic Finite State Machine）は、状態と入力によって次に遷移すべき状態が一意に定まる有限オートマトンである。DFA と略記される。
出典: フリー百科事典『ウィキペディア（Wikipedia）』

決定性有限オートマトンの定義

決定性有限オートマトン（DFA）とは、以下で定義される「５つ組」$(Q, Σ, δ , q_0, F)$ である。 $$ \begin{align} & Q : 状態集合 \\ & Σ : 入力アルファベット \\ & δ : Q × Σ から Q への遷移関数 \\ & q_0 : 開始状態(q_0 ∈ Q) \\ & F : 受理状態の集合(F ⊆ Q) \\ \end{align} $$ $集合 Q, Σ, A $ はいずれも有限集合である。

決定性有限オートマトンの具体例

上の定義だけ読むと意味不明ですが、具体的に考えると分かりやすいです。

英語版の wikipedia から例を借り、以下のようなDFA $M$ を考えます。

$$ \begin{align} & Q = \{ S_1, S_2 \} \\ & Σ = \{0, 1\} \\ & q_0 = S_1 \\ & F = \{S_1\}\\ & δ : 以下の状態遷移表により定義される。 \\ \end{align} $$

	0	1
S₁	S₂	S₁
S₂	S₁	S₂

登場する文字は $0$ か $1$ 、$ S_1$ の状態から始まって $0$ か $1$ のどちからが来ると、状態遷移表に従って、次の状態に移行します。

最終的に $ S_1$ の状態になる文字列は受理されます。

例えば、「00」「010」「100」「111」といった文字列は、最終的に $ S_1$ に辿り着き受理されます。

「 01」「101」「001」「0010」といった文字列は、 $ S_1$ に辿り着くことができず受理されません。

状態遷移図で表すと、以下のように表すことができます。

つまり、文字列の検索にオートマトンを使うと、まずはパターンに従い状態遷移図を作成し、次に文字列が状態遷移図によって最終的に受理されるかどうかを調べることで、文字列がパターンにマッチングするかどうかを調べることができます。