以前の記事で**閏年を判定する決定性有限オートマトン（DFA）**をコード化した。そのDFA自体は紙と鉛筆で頑張って作ったのだが、後になって機械任せで作れたのでその方法をまとめておく。
※コードを簡潔にするために、1桁も入力しなかった場合はゼロと見なして受理するように変更した。また、状態名もコードが出力する番号に合わせた。
手順
- 「入力値を400で割った余り」を状態に持つDFAを作成する
- 閏年を表す状態（97個）を受理状態とする
- DFAの状態数最小化を実行する
流れは単純だが人力でやるには厳しい大きさなので、コードを書いて実行する。
コード
状態数を最小化するアルゴリズムには、Hopcroftの最小化法から効率化部分を削って簡単にしたものを使っている。
BASE = 10
N = 400
# 閏年判定DFAを定義する
alphabets = *(0...BASE)
all_states = *(0...N)
accept_list = all_states.select { |m| m % 4 == 0 } - [100, 200, 300]
transitions = all_states.map do |m|
alphabets.map { |digit| (m * BASE + digit) % N }
end
# 状態数を最小化する（等価な状態をグループ化する）
state_groups = [accept_list, all_states - accept_list]
work_list = [accept_list]
while (states_to = work_list.shift)
alphabets.each do |digit|
# 各グループ内の状態を、入力 `digit` で遷移したときに
# `states_to` 内の状態になるかどうかで細分化
state_groups.map! do |states_from|
group1, group2 = states_from.partition do |m|
states_to.include?(transitions[m][digit])
end
if group1.empty? || group2.empty?
[states_from]
else
work_list << group1
[group1, group2]
end
end.flatten!(1)
end
end
# 等価な状態に同じ番号を振る
state_groups.each do |states|
states.each { |m| all_states[m] = states[0] }
end
# 最小化したDFAの状態遷移を出力する
state_groups.map(&:first).sort!.each do |m|
accept = accept_list.include?(m)
transition = transitions[m].map(&all_states.method(:[]))
transition_group = alphabets.group_by(&transition.method(:[])).invert
puts "#{m}\t#{accept}\t#{transition_group}"
end
0 true {[0, 4, 8]=>0, [1, 3, 5, 7, 9]=>1, [2, 6]=>2}
1 false {[0]=>10, [1, 3, 5, 7, 9]=>1, [2, 6]=>0, [4, 8]=>2}
2 false {[0]=>20, [1, 3, 5, 7, 9]=>1, [2, 6]=>2, [4, 8]=>0}
10 false {[0]=>100, [1, 3, 5, 7, 9]=>1, [2, 6]=>2, [4, 8]=>0}
20 true {[0]=>200, [1, 3, 5, 7, 9]=>1, [2, 6]=>2, [4, 8]=>0}
100 false {[0]=>200, [1, 3, 5, 7, 9]=>1, [2, 6]=>2, [4, 8]=>0}
200 false {[0, 4, 8]=>0, [1, 3, 5, 7, 9]=>1, [2, 6]=>2}
※DFAの初期状態は 0。
解説
余りを求めるDFA
何桁あるのか事前に分からない数字を上から1桁ずつ入力して、それを4で割った余りがいくつになるか求めることを考える。入力した全部の桁（1億桁なら40MB以上）を覚えておかないと答えは出せないだろうか？
実際はそんなことは無く、これまで入力した数を4で割った余りさえ覚えておけば、1桁増えた時の余りを求められる。例えば 1234 % 4 = 2 なので、12345 % 4 = (1234 * 10 + 5) % 4 = (2 * 10 + 5) % 4 = 1 となる。
\begin{align}
m_{n+1} &\equiv m_{n} \cdot 10 + digit_{n+1} \pmod 4 \\
m_{0} &= 0 \\
\end{align}
「現時点での余り」と「次の桁の入力」が決まれば一意に「新しい余り」が決まるので、余りを状態としたDFAを構築できる。4で割った余りなら下図の通り、0～3の4状態を持つ。12345 を入力すれば 0 → 1 → 0 → 3 → 2 → 1 と遷移して、余りは1と分かる。
この方法は4だけでなく任意の数で割った余りに対して使える。更には十進法以外でも構わない。
余りによる閏年の判定
閏年は400年周期で全く同じパターンになるため、年を400で割った余りによって閏年か平年かが分かる。余りを求めるDFAは前節の通り余りの種類だけ状態を用意すれば簡単に作れるので、後は各状態を閏年→受理、平年→非受理とすれば、閏年を判定するDFAの完成となる。
400状態もあるDFAはさすがに図にしづらいので省略。
状態数最小化
同じ入力に対して同じ結果を返してくれれば、2つのDFAは等価といえる。等価なDFAをどれかひとつ作るなら、なるべくシンプルな形を選びたいところ。DFAにおいては状態の数を最小にするのが合理的で、定義がコンパクトになるだけでなく、等価な最小DFAは1種類しかない（異なる形は作れない）という綺麗な性質がある。
一方で、最小でないDFAには互いに区別する必要が無い状態が存在する。例えば400状態を持つ閏年DFAなら、[1, 41, 81, ..., 361] はどれも受理状態でない上に同じ遷移規則を持つ。こういうのを見つけて纏めていけば最小化できそうである。
しかし複雑なDFAになると、遷移規則が異なるのに区別しなくていい状態というのが存在するので、同じ遷移規則を見つける方法では最小化しそびれてしまう。そこで逆に、確実に異なる遷移規則を持つ状態同士を次々と区別していき、最後まで区別されなかったものを同じ状態と見なすことで、漏れなく最小化できる。「確実に異なる遷移規則」というのは、同じ文字を入力したのに異なる（区別される）状態に遷移するものが1文字でも存在する場合を言う。
閏年DFAの例なら、0 と 20 はどちらも受理状態だが、0を入力するとそれぞれ 0（受理）と 200（非受理）に遷移するので互いに区別される。それが分かると、次は 200 と 2 が互いに区別されることも明らかになる。これを $_{400}C_{2}$ 通りの組み合わせから全てあぶり出せばいい、というのが最小化法のひとつ。
コードに用いたHopcroftの最小化法では、最初は状態を受理/非受理で大雑把にグループ分けしておいて、それを次第に細分化していく。最終的には等価な状態がひとつのグループにまとまり、遷移はグループ間で行われる形になる。最小化の途中段階では、あるグループが細分化されると、そのグループに遷移していたグループも細分化される可能性がある。
閏年DFAの状態 [0, 2, 20, 200] のみについてアルゴリズムを適用すると、下図のように細分化されていく。第1ステップ（右～中央）では [2, 200] → [0, 20] というグループ間での遷移が成立しているが、[0, 20] が細分化された後の第2ステップ（中央～左）では [2, 200] も細分化されることになる。実際には400状態・10文字を一斉に扱うので、同じグループには大量の状態が入っているし、遷移の矢印も膨大になる。
余談
閏年DFAを手作業で作ったときは、最初に「4の倍数を判定するDFA」（状態 [0, 1, 2]）を作ってから、100の倍数を扱うために入力 0 のときに別の状態（[10, 20, 100, 200]）へ遷移させるように拡張した。閏年の規則の簡潔さと入力が十進数であることを利用したので、初めから最小に近いDFAを作ることができた。
機械的に作る方法なら、十六進数で年を入力した場合の判定や、修正ユリウス暦での閏年の判定、より一般にはNで割った余りで判定できる事柄全ての最小DFAが同じように作れる。問題毎に楽する工夫を考える必要は無く、一旦コード化しておけば地道な最小化も勝手にやってくれる。