非決定性automatonのsubset construction
同じ文字列を読んでも、たどる経路によって到達状態が変わる有限オートマトンを、非決定性有限オートマトン(NFA: nondeterministic finite automaton)という。
概要
異なる文字列を数えたいとき、NFAの経路ごとに数えると同じ文字列を重複して数えてしまう。
そこで、一つの文字列を読んだ後に到達し得る状態を全て集め、その集合を新しい一状態にする。次の文字を決めれば次の集合は一意に決まるので、決定性有限オートマトン(DFA: deterministic finite automaton)として扱える。この変換が部分集合構成(subset construction)である。以下、入力に使う文字の有限集合をアルファベットとし、文字列を「語」とも呼ぶ。
考え方
二本の経路でも語は一つ
独自の小例として、初期状態の候補を とし、文字aを読む辺が 、 の二本あるとする。経路は二本でも、読んだ語はaの一つだけである。到達可能な状態を集合にすれば、どちらの経路も同じ要素 となり、次状態は 一つになる。
重要なのは、到達状態を一つ選ぶのでも、到達経路の本数を残すのでもなく、その語で到達できる状態の全体を残すことである。次に読める文字は現在状態からの辺だけで決まるため、この集合があれば語の古い部分や経路を覚える必要はない。
文字を読まない移動も集合へ含める
文字を一つも読まずに移動できる辺をε遷移という。εは空文字列を表し、アルファベットの一文字としては数えない。状態集合 からε遷移だけを0回以上たどって到達できる全状態をε閉包 とする。0回の移動も含めるので である。
元の状態 から文字 を一つ読んで直接移れる状態の集合を とし、受理状態の集合を とする。NFAが語を受理するとは、その語を全て読んだ後に 内の状態へ至る経路が少なくとも一つあることをいう。DFAの初期状態 と、集合 から文字 を読む遷移 は次のように定める。
現在集合には既にε閉包を取ってあるので、文字を読む前に可能なε移動も含まれている。集合内の各状態から の辺をたどり、その行き先を和集合でまとめ、さらに文字を読んだ後のε移動を含める。ε遷移がなければ としてよい。
先ほどの例に、文字bを読む辺 と、文字を読まない辺 を加え、 とする。アルファベットはaとbで、これ以外の辺はない。初期集合は のままだが、aを読んだ後は となる。 から へのε移動で長さを増やさずに受理できる。
受理判定は であり、集合の全要素が受理状態である必要はない。この例では長さ0の空文字列は受理されず、長さ1のaとbは受理される。一方、aaでは二文字目を読める状態がなく、到達集合は空集合になる。空集合からはどの文字でも空集合へ戻り、以後の文字で復活しない。
集合の遷移と、語の個数の加算を分ける
拡張した例では、aとbはどちらも集合 へ至る。到達集合が同じでも、この二語は異なるので個数は2である。ここでは二種類の合流を区別する。
- 同じ語の複数経路は、遷移先の和集合で重複を消す。
aの二経路があっても、語は一つである。 - 異なる語が同じ集合へ至るときは、語の個数を加算する。集合を訪問済みとして個数まで1にしてはいけない。
具体的には、 を「長さ の語のうち、到達可能集合がちょうど である語の個数」と定める。初期値は空文字列の一通りに対応する とし、他は0にする。長さ の層から、アルファベットの各文字 について次の層へ加える。
異なる文字が同じ集合へ移る場合も、文字ごとに加算する。この例なら となる。長さ の受理される語の個数は次の和で得られる。
空集合のDP値には実現できない語が集まるが、受理条件を満たさず答えに入らない。受理される語だけを数える実装なら、空集合への遷移を捨ててもよい。長さ0を問われた場合も、 が空でなければ空文字列の一通り、空なら0となる。
ABC228 G「Digits on Grid」はこの区別を使う問題である。全マスが1の 盤面で操作を一周、すなわち とすると、コマの初期位置や移動先の選び方は複数あっても、長さ2の数字列は11だけである。行と列を頂点、各マスをその数字のラベルが付いた辺とみなすと、初期集合は全行、1を読むと全列、さらに1を読むと全行になる。これらの集合へ経路数を加えるのではなく、語1、語11をそれぞれ一通りとして伝える。全頂点を受理状態にすれば、指定長を読んだ後の非空集合が受理される。この問題にε遷移はない。
到達する集合だけを作る手順と正当性
初期集合 にIDを割り当て、キューへ入れる。未処理の集合を取り出し、各文字について を計算する。既知集合ならそのIDへの辺を記録し、未知集合なら新しいIDを割り当ててキューへ追加する。この幅優先探索(BFS)で到達する集合だけを生成できる。元の状態が少数なら、集合をbitmaskで表し、和集合をビットORで計算できる。BFSは集合と遷移表を作る処理であり、語の個数は別途、長さ順のDPで求める。
正しさの核は「ある語を読んだDFAの状態が、その語を読んでNFAで到達できる状態のちょうど全体になる」という不変条件である。空文字列では なので成立する。先頭から読んだ部分(prefix)について成立していれば、次の文字を読む経路は、現在集合のどれかからその文字の辺を一本たどり、その後にε遷移をたどる経路の全てである。従って上の和集合と閉包が、漏れも余分もなく次の到達集合を与える。最後に と交わるかを調べれば、元のNFAと同じ語を受理する。
さらに、一つの語からDFA上の経路は一意に決まり、長さ の語は「長さ のprefixと末尾の一文字」へ一意に分解できる。このためDPは、同じ語を二度足さず、全ての語を数えられる。同じ到達集合の語は、その後に同じ文字を追加したときも同じ集合へ移るので、個数だけをまとめて保持してよい。
成立条件と計算量
元の状態数を 、アルファベットの文字数を 、初期集合から到達する集合の数を とすると、 である。BFSで未到達集合を省いても、最悪の場合の指数的な増加はなくならない。元状態が少ないか、到達集合が小さく収まる根拠が必要である。ABC228 Gでは偶数文字後は行だけ、奇数文字後は列だけの集合になるため、行数 、列数 に対して集合数を 以下に抑えられる。
集合と文字の組は 個あるが、一遷移を常に定数時間とはみなせない。各状態の遷移先集合のOR、ε閉包の計算、集合の照合・登録を含む一遷移の費用を とすると、遷移表の構築は前処理を除いて 時間となる。bitmaskが一つの機械語に収まっても、集合内の元状態を全て走査してORすれば、その走査費用がかかる。複数の機械語が必要な集合ではOR自体にも長さに応じた費用がある。ε閉包を前計算するなら、その時間と保存領域も別に加える。
構築済みの遷移表で長さ までDPする時間は 、従って構築と合わせて に前処理時間を加えたものとなる。これはID参照と個数の加算を定数時間とする評価であり、法を取らず巨大な整数を扱うなら加算の桁数も考慮する。空間は、元のNFAと前処理に加えて、集合の保存が bit、遷移表が 個のID、二層分のDPが 個の値である。
復習では、数える対象が経路か語かを先に確かめる。同じ語に対応する可能状態は集合へまとめ、異なる語の個数は残す。その集合だけで未来の遷移と受理が決まること、集合数と一遷移の費用が制約に収まることを確認して使う。
問題一覧
- ABC228 G「Digits on Grid」 公式問題
技能・出典
主題: 非決定性automatonのsubset construction(同時に存在し得るNFA状態集合を一つのDFA状態とし、文字ごとの集合遷移と受理条件を構成する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。追加で学ぶ技能: automaton上のDP・行列遷移(位置・長さとautomaton stateの積状態を作り、禁止条件を満たす遷移を除き、処理終了時に目的言語の受理状態を集計する。禁止パターン回避では検出状態を除外し、全パターン充足では出現maskが全て立つ状態を受理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 部分集合・bitmask状態DP(bitmaskの各bitが表す意味を定め、部分集合間の遷移を正しく設計できる。)。主タグ: automaton上のDP・行列遷移、非決定性automatonのsubset construction / 補助タグ: 部分集合・bitmask状態DP
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
前提・学習成果・出典
習得対象の目安: 黄色(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の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。