部分集合構成法

部分集合構成法（ぶぶんしゅうごうこうせいほう、英: 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つ組 ${\displaystyle (Q,\Sigma ,\delta ,q_{0},A)}$ を以って定める。このNFAを部分集合構成法を用いて変換するとDFA ${\displaystyle ({\mathcal {P}}(Q),\Sigma ,\delta ',\{q_{0}\},F')}$ が得られる。ただし、

• ${\displaystyle \delta '(R,a)=\bigcup _{r\in R}\delta (r,a)}$
• ${\displaystyle F'=\{R\in {\mathcal {P}}(Q)|R\cap F\neq \emptyset \}}$

である^{[注 1][3][4]}。

上述の方法は最も単純な方法であるが、初期状態から到達できない状態が大量に生成される可能性がある。これを避けるためには、初期状態から任意の文字列を与えて遷移を行うことを繰り返し、実際に到達できた状態集合だけを変換後の状態とする必要がある^[5][6]。

ε-遷移を伴うNFAの場合

ε-遷移を許すNFAに対しては、ある状態に対してそこからε-遷移のみで到達可能な状態の集合（ε-閉包）を考える必要がある。ε-遷移を伴うNFAについて、van Noordは3つの対処法が考えられるとした^[7]。

• 変換前のNFAの状態それぞれのε-閉包を考慮し、ε-遷移を伴わないNFAを生成してから部分集合構成法を適用する方法。3つの中で最も実装が簡単であるが、自然言語処理の際によく生じるような、ε-遷移を多く含むNFAに対しては実用的ではないことがある。
• 部分集合構成法の計算中において、変換前のNFAの各状態ごとにε-閉包を計算する方法。状態が現れるたびにε-閉包を計算しても良いし、最初に到達した時点の計算結果をキャッシュとして保持しておいても良い。
• 部分集合構成法の計算中において、変換後のDFAの各状態ごと、すなわち変換前のNFAの状態の集合ごとにε-閉包を計算する方法。

初期状態が複数存在するNFAの場合

初期状態が複数存在するNFA^[8]に対しては以下の2つの対処が考えられる。

• 初期状態全てからなる集合を考え、これに対応するDFAでの状態を初期状態とする。
• 変換しようとするNFAがε-遷移を許すならば、新たに状態を1つ加えてこれを初期状態とし、元の初期状態それぞれへε-遷移できるように遷移規則を書き換える。

NFAの認識する言語

上で示したアルゴリズムにより任意のNFAに対し等価なDFAを構成できることが分かった。一方で任意のDFAに対してもそれと等価なNFAを構築することができる。すなわち、DFA ${\displaystyle (Q,\Sigma ,\delta ,q_{0},F)}$ に対しては、${\displaystyle \delta '(q,a)=\{\delta (q,a)\}}$ を用いたNFA ${\displaystyle (Q,\Sigma ,\delta ',q_{0},F)}$ を考えれば良い^[9]。これにより、ある言語が正規であることと、あるNFAによって認識されることが同値であることが示される^[10]。

例

下の状態遷移図で示されるNFAを例に取る。このNFAは4つの状態からなり、状態 ${\displaystyle 1}$ が初期状態、状態 ${\displaystyle 3}$、${\displaystyle 4}$ が受理状態であり、遷移規則にはε-遷移を含む。またアルファベットは ${\displaystyle \{0,1\}}$ である。

変換後のDFAにおける初期状態は、NFAの初期状態である状態 ${\displaystyle 1}$ のε-閉包を考えれば良く、今回の例では ${\displaystyle \{1,2,3\}}$ である。次に状態 ${\displaystyle \{1,2,3\}}$ において入力 ${\displaystyle 0}$ が与えられた際の遷移について、状態 ${\displaystyle 1}$ から状態 ${\displaystyle 2}$ への遷移と状態 ${\displaystyle 2}$ から状態 ${\displaystyle 4}$ への遷移が考えられる。ここで状態 ${\displaystyle 2}$ 及び ${\displaystyle 4}$ はいずれもε-遷移を持たないから、${\displaystyle \delta '(\{1,2,3\},0)=\{2,4\}}$ であることが分かる。以降このようにして、変換後の遷移規則の検討を新しい状態の集合が発生するたびに行う。すると下に示されるようなDFAが得られる。

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

計算量

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

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

応用

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

脚注

注釈

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

出典

1. 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. 
2. Sipser 2008, pp. 63–64.
3. Sipser 2008, pp. 64–65.
4. Hopcroft, Motwani & Ullman 2006, pp. 60–61.
5. Appel, Andrew W.『最新コンパイラ構成技法』神林靖・滝本宗宏 訳、翔泳社、2009年10月29日（原著1999年）、24-25頁。ISBN 9784798114682。 
6. ^ Schneider, Klaus (2004). Verification of reactive systems: formal methods and algorithms. Springer. pp. 210–212. ISBN 978-3-540-00296-3. https://books.google.com/books?id=Z92bL1VrD_sC&pg=PA210 
7. 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. http://www.mitpressjournals.org/doi/pdfplus/10.1162/089120100561638. 
8. Rothe, Jörg (2006). Complexity Theory and Cryptology: An Introduction to Cryptocomplexity. Texts in Theoretical Computer Science. Springer. pp. 21–22. ISBN 9783540285205. https://books.google.com/books?id=YnLmsHAtvYEC&pg=PA21 
9. Hopcroft, Motwani & Ullman 2006, pp. 64.
10. Sipser 2008, p. 65-66.
11. Appel 2009, p. 24.
12. 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。
13. Hopcroft, Motwani & Ullman 2006, pp. 64–65.
14. 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 

関連項目

• 有限オートマトン
• 組合せ爆発