部分集合構成法
ウィキペディア フリーな encyclopedia
部分集合構成法(ぶぶんしゅうごうこうせいほう、英: subset construction)あるいは冪集合構成法(べきしゅうごうこうせいほう、英: powerset construction)とは、計算理論において非決定性有限オートマトン(NFA)を等価な決定性有限オートマトン(DFA)へと変換するための標準的な手法である。本手法はDFAとNFAが同じ能力であることを示すことから理論上重要であるとされる。また実用の面においても、本手法を用いることにより、柔軟に構築できるNFAを実行効率で勝るDFAに変換できるため、極めて有用である。一方、本手法により生成されるDFAの状態数は、変換前のNFAの状態から指数関数的に増大する可能性があり、このため巨大なNFAから生成されるDFAは全く実用的でない場合がある。
オートマトンにおける他の類似の構成法との区別のため、NFAをDFAに変換するこの手法はラビン-スコット冪集合構成法(あるいは部分集合構成法)と呼ばれることがある。これは本手法を1959年に初めて提案したマイケル・ラビンとデイナ・スコットにちなむ[1]。