部分集合構成法とは？わかりやすく解説

部分集合構成法（ぶぶんしゅうごうこうせいほう、英: subset construction）あるいは冪集合構成法（べきしゅうごうこうせいほう、英: powerset construction）とは、計算理論において非決定性有限オートマトン（NFA）を等価な決定性有限オートマトン（DFA）へと変換するための標準的な手法である。本手法はDFAとNFAが同じ能力であることを示すことから理論上重要であるとされる。また実用の面においても、本手法を用いることにより、柔軟に構築できるNFAを実行効率で勝るDFAに変換できるため、極めて有用である。一方、本手法により生成されるDFAの状態数は、変換前のNFAの状態から指数関数的に増大する可能性があり、このため巨大なNFAから生成されるDFAは全く実用的でない場合がある。

オートマトンにおける他の類似の構成法との区別のため、NFAをDFAに変換するこの手法はラビン-スコット冪集合構成法（あるいは部分集合構成法）と呼ばれることがある。これは本手法を1959年に初めて提案したマイケル・ラビンとデイナ・スコットにちなむ^[1]。

概要

DFAの実行をシミュレートする場合、たった1つの状態を追い続けることになる。つまり、初期状態から始め、入力を1文字読むたびに遷移規則によりただ一つに定まる新しい状態へと注目を移す。一方、NFAの実行のシミュレーションでは追うべき状態が複数になりうる。すなわち、ある文字を読み遷移した後の状態全てを把握しなければならない。ここで、NFAにおける状態の集合をDFAにおける1つの状態であると考えると、NFAのシミュレーションはDFAのシミュレーションであると捉えられるようになる^[2]。

構成法

まず単純な場合として、文字を読み取らずとも遷移すること（いわゆるε-遷移）を許さないNFAを考える。このようなNFAを5つ組 $(Q,\Sigma ,\delta ,q_{0},A)$

変換後のDFAにおける初期状態は、NFAの初期状態である状態 $1$

今回の例では、変換前のNFAは4状態からなるため状態の冪集合の大きさは16であるが、実際に到達可能な状態の集合はたったの5つである。

計算量

5状態からなるNFA（左）と16状態からなるDFA（右）はいずれも同じ言語を認識する^[6]

変換後のDFAの状態数は変換前のNFAに依存する。NFAの状態数が $n$ であるとき、DFAの状態数は最大で $2^{n}$ となりうる^[11]。特に、任意の自然数 $n$ に対して、 $n$ 個の状態からなるNFAであって、変換後のDFAの状態数が $2^{n}$ である、すなわち初期状態から任意の状態の部分集合に到達可能であるものが存在することが知られており、故に最悪計算量が $\Theta (2^{n})$ となることが示されている^[12]。変換後のDFAの状態数が非常に大きくなる例として、 $\{0,1\}$ をアルファベットとし、最後から $n$ 番目の要素が $1$ であるような文字列を受理するオートマトンを考える。これをNFAで構築した場合状態数は $n+1$ となるが、DFAでは $2^{n}$ 個の状態を要する^[13]^[6]。図は $n=4$ におけるNFAとDFAの状態遷移図である。

応用

DFA最小化に関するBrzozowskiのアルゴリズムは内部で部分集合構成法を用いる。具体的には、まず与えられたDFAの遷移規則全てを逆向きにし、また初期状態と受理状態を入れ替えることにより、元のDFAが受理する全ての文字列の逆順^{[注 2]}をちょうど受理するNFAを得る。次にこのNFAに対して部分集合構成法を適用して等価なDFAへと変換する。この手続きをもう一度繰り返すことにより、元のDFAと等価でかつ状態数最小のDFAが得られる。このアルゴリズムは前述の通り部分集合構成法を用いるため、その最悪計算量は指数オーダーとなる^[14]。

脚注

[脚注の使い方]

注釈

^ ここで用いた5つ組の定義は非決定性有限オートマトン#形式的定義および決定性有限オートマトン#形式的定義をそれぞれ参照せよ。
^ 文字列 $w=w_{1}w_{2}\cdots w_{n}$ に対し、 $w_{n}\cdots w_{2}w_{1}$ を $w$ の逆順と呼ぶ。

出典

^ Rabin, M. O.; Scott, D. (1959). “Finite automata and their decision problems”. IBM Journal of Research and Development 3 (2): 114–125. doi:10.1147/rd.32.0114. ISSN 0018-8646.
^ Sipser 2008, pp. 63–64.
^ Sipser 2008, pp. 64–65.
^ Hopcroft, Motwani & Ullman 2006, pp. 60–61.
^ Appel, Andrew W.『最新コンパイラ構成技法』神林靖・滝本宗宏訳、翔泳社、2009年10月29日（原著1999年）、24-25頁。ISBN 9784798114682。
^ ^a ^b ^c Schneider, Klaus (2004). Verification of reactive systems: formal methods and algorithms. Springer. pp. 210–212. ISBN 978-3-540-00296-3
^ Van Noord, Gertjan (2000). “Treatment of epsilon moves in subset construction”. Computational Linguistics 26 (1): 61–76. arXiv:cmp-lg/9804003. doi:10.1162/089120100561638.
^ Rothe, Jörg (2006). Complexity Theory and Cryptology: An Introduction to Cryptocomplexity. Texts in Theoretical Computer Science. Springer. pp. 21–22. ISBN 9783540285205
^ Hopcroft, Motwani & Ullman 2006, pp. 64.
^ Sipser 2008, p. 65-66.
^ Appel 2009, p. 24.
^ Meyer, A. R.; Fischer, M.J. (1971). "Economy of description by automata, grammars, and formal systems". Proceedings of SWAT 1971. IEEE. pp. 188–191. doi:10.1109/SWAT.1971.11。
^ Hopcroft, Motwani & Ullman 2006, pp. 64–65.
^ Brzozowski, J. A. (1963). "Canonical regular expressions and minimal state graphs for definite events". Proc. Sympos. Math. Theory of Automata (New York, 1962). Brooklyn, N.Y.: Polytechnic Press of Polytechnic Inst. of Brooklyn. pp. 529–561. MR 0175719。

参考文献

Sipser, Michael『計算理論の基礎 [原著第2版] 1.オートマトンと言語』太田和夫・田中圭介監訳阿部正幸・植田広樹・藤岡淳・渡辺治訳、共立出版、2008年5月25日（原著2006年）。ISBN 9784320122079。
Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2006). Introduction to Automata Theory, Languages, and Computation 3rd Edition. Reading Massachusetts: Addison-Wesley. ISBN 0-321-45536-3

部分集合構成法とは？わかりやすく解説