非決定性automatonのsubset construction

同じ文字列を読んでも、たどる経路によって到達状態が変わる有限オートマトンを、非決定性有限オートマトン(NFA: nondeterministic finite automaton)という。

概要

異なる文字列を数えたいとき、NFAの経路ごとに数えると同じ文字列を重複して数えてしまう。

そこで、一つの文字列を読んだ後に到達し得る状態を全て集め、その集合を新しい一状態にする。次の文字を決めれば次の集合は一意に決まるので、決定性有限オートマトン(DFA: deterministic finite automaton)として扱える。この変換が部分集合構成(subset construction)である。以下、入力に使う文字の有限集合をアルファベットとし、文字列を「語」とも呼ぶ。

考え方

二本の経路でも語は一つ

独自の小例として、初期状態の候補を I={u,v}I=\{u,v\} とし、文字aを読む辺が u→awu\xrightarrow{a}w、v→awv\xrightarrow{a}w の二本あるとする。経路は二本でも、読んだ語はaの一つだけである。到達可能な状態を集合にすれば、どちらの経路も同じ要素 ww となり、次状態は {w}\{w\} 一つになる。

重要なのは、到達状態を一つ選ぶのでも、到達経路の本数を残すのでもなく、その語で到達できる状態の全体を残すことである。次に読める文字は現在状態からの辺だけで決まるため、この集合があれば語の古い部分や経路を覚える必要はない。

文字を読まない移動も集合へ含める

文字を一つも読まずに移動できる辺をε遷移という。εは空文字列を表し、アルファベットの一文字としては数えない。状態集合 AA からε遷移だけを0回以上たどって到達できる全状態をε閉包 E(A)E(A) とする。0回の移動も含めるので A⊆E(A)A\subseteq E(A) である。

元の状態 vv から文字 cc を一つ読んで直接移れる状態の集合を δ(v,c)\delta(v,c) とし、受理状態の集合を FF とする。NFAが語を受理するとは、その語を全て読んだ後に FF 内の状態へ至る経路が少なくとも一つあることをいう。DFAの初期状態 A0A_0 と、集合 AA から文字 cc を読む遷移 TT は次のように定める。

A0=E(I),T(A,c)=E(⋃v∈Aδ(v,c))A_0=E(I),\qquad T(A,c)=E\left(\bigcup_{v\in A}\delta(v,c)\right)

現在集合には既にε閉包を取ってあるので、文字を読む前に可能なε移動も含まれている。集合内の各状態から cc の辺をたどり、その行き先を和集合でまとめ、さらに文字を読んだ後のε移動を含める。ε遷移がなければ E(A)=AE(A)=A としてよい。

先ほどの例に、文字bを読む辺 u→bwu\xrightarrow{b}w と、文字を読まない辺 w→εfw\xrightarrow{\varepsilon}f を加え、F={f}F=\{f\} とする。アルファベットはaとbで、これ以外の辺はない。初期集合は {u,v}\{u,v\} のままだが、aを読んだ後は {w,f}\{w,f\} となる。ww から ff へのε移動で長さを増やさずに受理できる。

受理判定は A∩F≠∅A\cap F\neq\varnothing であり、集合の全要素が受理状態である必要はない。この例では長さ0の空文字列は受理されず、長さ1のaとbは受理される。一方、aaでは二文字目を読める状態がなく、到達集合は空集合になる。空集合からはどの文字でも空集合へ戻り、以後の文字で復活しない。

集合の遷移と、語の個数の加算を分ける

拡張した例では、aとbはどちらも集合 {w,f}\{w,f\} へ至る。到達集合が同じでも、この二語は異なるので個数は2である。ここでは二種類の合流を区別する。

  • 同じ語の複数経路は、遷移先の和集合で重複を消す。aの二経路があっても、語は一つである。
  • 異なる語が同じ集合へ至るときは、語の個数を加算する。集合を訪問済みとして個数まで1にしてはいけない。

具体的には、dp[k][A]dp[k][A] を「長さ kk の語のうち、到達可能集合がちょうど AA である語の個数」と定める。初期値は空文字列の一通りに対応する dp[0][A0]=1dp[0][A_0]=1 とし、他は0にする。長さ kk の層から、アルファベットの各文字 cc について次の層へ加える。

dp[k+1][T(A,c)]+=dp[k][A]dp[k+1][T(A,c)]\mathrel{+}=dp[k][A]

異なる文字が同じ集合へ移る場合も、文字ごとに加算する。この例なら dp[1][{w,f}]=2dp[1][\{w,f\}]=2 となる。長さ LL の受理される語の個数は次の和で得られる。

∑A: A∩F≠∅dp[L][A]\sum_{A:\,A\cap F\neq\varnothing}dp[L][A]

空集合のDP値には実現できない語が集まるが、受理条件を満たさず答えに入らない。受理される語だけを数える実装なら、空集合への遷移を捨ててもよい。長さ0を問われた場合も、A0∩FA_0\cap F が空でなければ空文字列の一通り、空なら0となる。

ABC228 G「Digits on Grid」はこの区別を使う問題である。全マスが1の 2×22\times2 盤面で操作を一周、すなわち N=1N=1 とすると、コマの初期位置や移動先の選び方は複数あっても、長さ2の数字列は11だけである。行と列を頂点、各マスをその数字のラベルが付いた辺とみなすと、初期集合は全行、1を読むと全列、さらに1を読むと全行になる。これらの集合へ経路数を加えるのではなく、語1、語11をそれぞれ一通りとして伝える。全頂点を受理状態にすれば、指定長を読んだ後の非空集合が受理される。この問題にε遷移はない。

到達する集合だけを作る手順と正当性

初期集合 A0A_0 にIDを割り当て、キューへ入れる。未処理の集合を取り出し、各文字について T(A,c)T(A,c) を計算する。既知集合ならそのIDへの辺を記録し、未知集合なら新しいIDを割り当ててキューへ追加する。この幅優先探索(BFS)で到達する集合だけを生成できる。元の状態が少数なら、集合をbitmaskで表し、和集合をビットORで計算できる。BFSは集合と遷移表を作る処理であり、語の個数は別途、長さ順のDPで求める。

正しさの核は「ある語を読んだDFAの状態が、その語を読んでNFAで到達できる状態のちょうど全体になる」という不変条件である。空文字列では E(I)E(I) なので成立する。先頭から読んだ部分(prefix)について成立していれば、次の文字を読む経路は、現在集合のどれかからその文字の辺を一本たどり、その後にε遷移をたどる経路の全てである。従って上の和集合と閉包が、漏れも余分もなく次の到達集合を与える。最後に FF と交わるかを調べれば、元のNFAと同じ語を受理する。

さらに、一つの語からDFA上の経路は一意に決まり、長さ k+1k+1 の語は「長さ kk のprefixと末尾の一文字」へ一意に分解できる。このためDPは、同じ語を二度足さず、全ての語を数えられる。同じ到達集合の語は、その後に同じ文字を追加したときも同じ集合へ移るので、個数だけをまとめて保持してよい。

成立条件と計算量

元の状態数を ss、アルファベットの文字数を qq、初期集合から到達する集合の数を RR とすると、R≤2sR\leq2^s である。BFSで未到達集合を省いても、最悪の場合の指数的な増加はなくならない。元状態が少ないか、到達集合が小さく収まる根拠が必要である。ABC228 Gでは偶数文字後は行だけ、奇数文字後は列だけの集合になるため、行数 HH、列数 WW に対して集合数を 2H+2W2^H+2^W 以下に抑えられる。

集合と文字の組は RqRq 個あるが、一遷移を常に定数時間とはみなせない。各状態の遷移先集合のOR、ε閉包の計算、集合の照合・登録を含む一遷移の費用を CC とすると、遷移表の構築は前処理を除いて O(RqC)O(RqC) 時間となる。bitmaskが一つの機械語に収まっても、集合内の元状態を全て走査してORすれば、その走査費用がかかる。複数の機械語が必要な集合ではOR自体にも長さに応じた費用がある。ε閉包を前計算するなら、その時間と保存領域も別に加える。

構築済みの遷移表で長さ LL までDPする時間は O(LRq)O(LRq)、従って構築と合わせて O(RqC+LRq)O(RqC+LRq) に前処理時間を加えたものとなる。これはID参照と個数の加算を定数時間とする評価であり、法を取らず巨大な整数を扱うなら加算の桁数も考慮する。空間は、元のNFAと前処理に加えて、集合の保存が O(Rs)O(Rs) bit、遷移表が O(Rq)O(Rq) 個のID、二層分のDPが O(R)O(R) 個の値である。

復習では、数える対象が経路か語かを先に確かめる。同じ語に対応する可能状態は集合へまとめ、異なる語の個数は残す。その集合だけで未来の遷移と受理が決まること、集合数と一遷移の費用が制約に収まることを確認して使う。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

前提・学習成果・出典

習得対象の目安: 黄色(2000–2399)。NFAの可能状態集合を一状態へ写し、受理条件と指数的な状態数を評価する。

対象色の読み方は本書の読み方を参照してください。

概念上の親: 禁止・要求patternを有限状態へ圧縮する。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-automaton-subset-construction

非決定性automatonのsubset construction

習得する技能

  • 同時に存在し得るNFA状態集合を一つのDFA状態とし、文字ごとの集合遷移と受理条件を構成する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: 有限状態automatonの構成。

このUnitを直接前提とする単元: なし。

有限状態automatonの構成で得た考え方と実装を再利用し、非決定性automatonのsubset constructionの発動条件・正当化・境界を重複なく学ぶ。

このUnitでは扱わないもの

  • 非決定性automatonのsubset constructionの発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠