部分集合構成法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/09/22 18:36 UTC 版)
部分集合構成法（ぶぶんしゅうごうこうせいほう、英: subset construction）あるいは冪集合構成法（べきしゅうごうこうせいほう、英: powerset construction）とは、計算理論において非決定性有限オートマトン（NFA）を等価な決定性有限オートマトン（DFA）へと変換するための標準的な手法である。本手法はDFAとNFAが同じ能力であることを示すことから理論上重要であるとされる。また実用の面においても、本手法を用いることにより、柔軟に構築できるNFAを実行効率で勝るDFAに変換できるため、極めて有用である。一方、本手法により生成されるDFAの状態数は、変換前のNFAの状態から指数関数的に増大する可能性があり、このため巨大なNFAから生成されるDFAは全く実用的でない場合がある。
注釈
- ^ ここで用いた5つ組の定義は非決定性有限オートマトン#形式的定義および決定性有限オートマトン#形式的定義をそれぞれ参照せよ。
- ^ 文字列 に対し、 を の逆順と呼ぶ。
出典
- ^ 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。
[続きの解説]
「部分集合構成法」の続きの解説一覧
- 1 部分集合構成法とは
- 2 部分集合構成法の概要
- 3 計算量
- 4 応用
- 部分集合構成法のページへのリンク
