これは ZOZO Advent Calendar 2022 カレンダー Vol.2 の 5 日目の記事です。
昨日の投稿は @umsys さんの「今話題のChatGPTと一緒にAndroidアプリを作ろう！」でした。
ZOZO Advent Calendar 2022 をご覧のみなさん、こんにちは。
ZOZO ML・データ部所属の @tama_Ud です。
今回はPythonでDFAを作りたいと思います。
擦り尽くされた車輪ですが、ホリデーシーズンにCSの学習をやり直すにはちょうど良いのではないでしょうか。
DFAとは
決定性有限オートマトン （Deterministic Finite Automaton） のことです。
有限オートマトンは有限個の状態と遷移と動作の組み合わせからなる数学的に抽象化された「ふるまいのモデル」- Wikipedia
大きく分けて「決定性」と「非決定性」があります。
決定性有限オートマトン : 状態と入力によって次に遷移すべき状態が一意に定まる
非決定性有限オートマトン : ある状態と入力があったとき、次の遷移先が一意に決定しないことがある
決定性有限オートマトン（以下DFA）は以下の５つ組で定義されます。
- $\varrho : 状態集合$
- $\sum : 入力アルファベット$
- $\delta : \varrho \times \sum から\varrhoへの遷移関数 (状態と入力を受け取り、状態を返す) $
- $q_0 : 開始状態 (q_0 \in \varrho)$
- $F : 受理状態の集合 (F \subseteq \varrho)$
$集合\varrho, \sum, Fはいずれも有限集合$
受理状態の定義
$M = (\varrho, \sum, \delta, q_0, F)$ を決定性有限オートマトン,
$\omega = \omega_1\omega_2...\omega_n$ を$\sum$ 上の長さ $n$ の文字列とする ($\omega \in \sum^n$)
$M$が$\omega$を受理するとは、状態の列$r_0,r_1...,r_n \in \varrho$ が存在する場合、次を満たすことです。
- $r_0 = q_0$
- $∀_i \in [n]\delta(r_{i-1}, \omega_i) = r_i$
- $R_n \in F$
$M$ に対して、$L(M)$ = { $\omega \in \sum^* : M$ が$\omega$ を受理する } とした時,
この時 $M$ が言語 $L(M)$ を認識するという。
DFAが認識する言語のクラスを $L_{DFA}$ と表記します。
（参考: オートマトンと言語理論）
DFAはよく自動販売機の販売システムで例えられます。
状態を自動販売機内のモード、入力を購入者の行動に当てはめてみます。
購入者は硬貨の投入、ボタンの押下によって購入操作を行い、商品を受け取ります（遷移関数で表せる）。
そしてまた最初の待機モードに遷移します。これが受理状態ですね。
待機モード [開始状態 = 状態0] ← 硬貨が投入される [入力0]
↓ [遷移関数: (0,0)->1]
商品選択モードになる [状態1] ← ボタンが押される [入力1]
↓ [遷移関数: (1,1)->0]
待機モードに戻る [受理状態 = 状態0 = 開始状態]
…
外部から一連の入力を受け取り、現在の内部状態を必ず一つの状態へと変化させる仕組みを持っていることがわかりますね。
処理は一本道ではなく、内部状態が変化しなかったり、前の状態に戻ったりもします。(投入された金額が商品の金額に満たない場合や, 商品を選ばないままタイムアウトした場合などが考えられますね)
「遷移すべき状態が一意に定まっているふるまい」のイメージが掴めたでしょうか。
あくまで例えなので、定義の部分をゆっくり読んでみるとより理解が深まります。
オートマトンとはなんぞやという話を深掘りし始めると素人の自分は大怪我をするため定義の引用にとどめます......。
実装
1. 5つ組の定義
まずDFAの5つ組を定義します。
# 5つ組を定義
# states = [0, 1, 2] # Q: int
# characters = ['0', '1'] # Σ: string
start = 0 # q0: int
accept = [0] # F: int
transition = {} # δ: map dict (現在のstate, 現在のinput) -> 次のstate
今回は簡単のためglobal変数に定義します。
statesとcharactersからtransitionを生成する場合はアンコメントし、関数を追記してください。
2. 遷移関数の定義
次に遷移関数を定義します。
状態遷移表や状態遷移図を用意するとわかりやすいです。
...
# δ: map dictionary (現在のstate, 現在のinput) -> 次のstate
transition = {
(0, '0'): 0, (0, '1'): 1,
(1, '0'): 2, (1, '1'): 0,
(2, '0'): 1, (2, '1'): 2,
}
3. 実行部分
実行部のコードは以下です。
def operation():
print("判定したい文字列を入力してください: ", end="")
str = input()
state = start
for s in str:
state = transition[(state, s)]
return state in accept
# $ python3 dfa.py
# 判定したい文字列を入力してください: 1001
# True
# $ python3 dfa.py
# 判定したい文字列を入力してください: 1010
# False
うまく実行できました。
状態遷移表の生成関数を定義するともっと柔軟に遊べそうですね。
終わりに
DFAの数学的な定義は一見とっつきにくいですが、実装はとても簡単（もちろんDFAモジュールを1から作るのは大変）なので皆さんもぜひ書いて楽しんでみてください。
ネタとしてはNFAからDFAへの変換、正規表現エンジン、パーサージェネレータの自作、俺俺言語の開発......とか大層なことを考えていたのですが、DFAの実装だけで終わってしまいました。車輪の再発明ですが、オートマトンの理解を少し深められたと思います。
明日は @pkino さんの「Google Mapsのデータを活用し、便利なGoogle My Mapsを作成する」です。
お楽しみに！
参考文献
Finite Automata: Simulate a DFA in Python 🐍
オートマトンは正規表現の夢を見るか(見るし、夢というかそのものですらある)
How are finite automata implemented in code?
オートマトンと言語理論
LR parsing
LR(1)パーサジェネレータを自作して構文解析をする 第1回:かんたん構文解析入門