Day 133-Q3 — Hopcroft's DFA Minimization Algorithm（決定性有限オートマトン最小化）

2026-08-25 赤色 Master / Phase 8+ ★★★★★★★★★ 逆遷移による分割精緻化 O(NK log N)

問題

$N$個の状態（$0$から$N-1$）とアルファベットサイズ$K$を持つ完全決定性有限オートマトン（DFA）が与えられる。状態$0$が初期状態、遷移関数$\delta(s,c)$と受理状態集合$F$が与えられる。

このDFAと等価な言語を受理する最小状態数のDFA（初期状態から到達可能な状態のみを対象とする）を、Hopcroftのアルゴリズム（分割精緻化）によって求め、その状態数を出力せよ。

入力形式

N K
delta[0][0] ... delta[0][K-1]
...
delta[N-1][0] ... delta[N-1][K-1]
|F|
f_1 f_2 ... f_|F|

制約

$1 \le N \le 300$
$1 \le K \le 5$
$0 \le \delta(s,c) < N$（完全DFA）
$0 \le |F| \le N$、$f_i$は相異なる

入出力例

入力例1

4 2
1 2
1 3
1 3
3 3
1
3

出力例1

3

状態1と状態2はどちらも「0で状態1へ、1で受理状態3へ」という同じ遷移を持ち等価。最小DFAは{0},{1,2},{3}の3状態。

概念図

DFA最小化: 状態1と状態2は同じ遷移パターン ⇒ 等価 ⇒ マージ Before（4状態） 0 1 2 3 1 0 0 0 1 1 After（最小化・3状態） 0 {1,2} 3 1 0 0 1 分割精緻化: 逆遷移X=δc⁻¹(A)でP内の各集合を割り、区別できた分だけ細分化する

ヒント（段階的開示）

ヒント1（方向性）

2つの状態が「等価（区別不可能）」とは、そこからどんな文字列を読んでも受理/非受理の結果が常に一致すること。「受理状態の集合」と「非受理状態の集合」という最も粗い2分割から始め、区別できる証拠が見つかるたびに分割を細かくしていくアプローチを考える。

ヒント2（アプローチ）

分割$P$と処理待ちworklist$W$を管理する。$W$から集合$A$を1つ取り出し、各文字$c$について「$c$を読むと$A$に入る状態の集合」$X=\delta_c^{-1}(A)$（逆遷移）を計算。$P$内の各集合$Y$について、$Y\cap X$と$Y\setminus X$が両方非空なら$Y$を2分割し、worklistには小さい方を追加する（これが$O(N\log N)$の鍵）。

ヒント3（誘導） 
rev = {c: {s: [] for s in reachable} for c in range(k)}
for s in reachable:
    for c in range(k):
        rev[c][delta[s][c]].append(s)

while W:
    A = W.pop()
    for c in range(k):
        X = set()
        for s in A: X.update(rev[c][s])
        if not X: continue
        newP = set()
        for Y in P:
            inter, diff = Y & X, Y - X
            if inter and diff:
                newP.add(frozenset(inter)); newP.add(frozenset(diff))
                if Y in W:
                    W.remove(Y); W.append(frozenset(inter)); W.append(frozenset(diff))
                else:
                    W.append(frozenset(inter) if len(inter)<=len(diff) else frozenset(diff))
            else:
                newP.add(Y)
        P = newP

模範解答 (Python)

import sys
from collections import deque

def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); k = int(data[idx + 1]); idx += 2
    delta = []
    for s in range(n):
        row = [int(data[idx + c]) for c in range(k)]
        idx += k
        delta.append(row)
    f_cnt = int(data[idx]); idx += 1
    accepting = set(int(data[idx + i]) for i in range(f_cnt))
    idx += f_cnt

    reach = set([0])
    dq = deque([0])
    while dq:
        s = dq.popleft()
        for c in range(k):
            t = delta[s][c]
            if t not in reach:
                reach.add(t)
                dq.append(t)

    F = frozenset(s for s in reach if s in accepting)
    NF = frozenset(reach - set(F))

    P = set()
    if F:
        P.add(F)
    if NF:
        P.add(NF)

    rev = [dict() for _ in range(k)]
    for c in range(k):
        for s in reach:
            rev[c].setdefault(delta[s][c], []).append(s)

    W = []
    if F and NF:
        W.append(F if len(F) <= len(NF) else NF)
    elif F:
        W.append(F)
    else:
        W.append(NF)

    while W:
        A = W.pop()
        for c in range(k):
            X = set()
            for s in A:
                if s in rev[c]:
                    X.update(rev[c][s])
            if not X:
                continue
            newP = set()
            changed = []
            for Y in P:
                inter = Y & X
                diff = Y - X
                if inter and diff:
                    fi, fd = frozenset(inter), frozenset(diff)
                    newP.add(fi)
                    newP.add(fd)
                    changed.append((Y, fi, fd))
                else:
                    newP.add(Y)
            for Y, fi, fd in changed:
                if Y in W:
                    W.remove(Y)
                    W.append(fi)
                    W.append(fd)
                else:
                    W.append(fi if len(fi) <= len(fd) else fd)
            P = newP

    print(len(P))

solve()

Step-by-Step 解説

1到達可能性の除去
初期状態からBFSして到達可能な状態集合を求め、以降の処理をそれに限定する。
2初期分割
「受理／非受理」で状態を2分割するのがスタート地点。これより粗い分割はあり得ない。
3逆遷移による細分化
worklistから取り出した$A$と文字$c$について$X=\delta_c^{-1}(A)$を求め、$Y\cap X$と$Y\setminus X$が両方非空な$Y$を2つに割る。
4worklistの管理（Hopcroftの工夫）
分割済み$Y$がworklistにあれば置き換え、なければ小さい方だけ追加する。これが各状態のworklist登場回数を$O(\log N)$回に抑える鍵。
5収束
worklistが空になった時点で、これ以上区別できる状態対は存在しない。このときの$|P|$が最小DFAの状態数。

よくあるミス

ミス原因正しい書き方
到達不能な状態を含めたまま最小化する等価性だけを見て到達可能性チェックを省略初期状態からBFSして到達可能集合を先に求め限定する
worklistに常に片方だけ積んでしまう「小さい方を積む」というHopcroftの工夫を理解していないlen(inter)<=len(diff)で小さい方を判定して積む
Yがworklistにある場合の置き換え処理を忘れる新しくできた2集合を追加するだけで済ませるY∈WならYを取り除いてから2集合を追加する
逆遷移を毎回O(N)の全状態走査で計算事前に逆遷移テーブルを構築していないrev[c][t]=[s: delta[s][c]==t]を前計算しておく

次のステップ

  • 発展: 最小化後の実際の遷移テーブル（代表状態を選んでの新しい$\delta'$）を復元して出力せよ。
  • 発展2: 正規表現→NFA（Thompson構成法）→部分集合構成法でDFA化→Hopcroftで最小化、という一連のパイプラインを実装し字句解析器の内部動作を追体験せよ。
  • 次回予告: 次回のテーマは今後のセッションで選定

自己評価

自分の回答

気づき・メモ