部分集合構成法

NFAにおいては「状態集合」から「状態集合」への遷移が行われていると考えることができるので、「状態集合」そのものを新たな「状態」とみなすことでDFAとして取り扱うことができる

「初期状態集合」から全ての入力記号を入力した時の「遷移先状態集合」を木構造で列挙していき、同じ状態集合が2度目に現れたタイミングで探索をストップする。

このように到達可能性判定とほぼ同じアルゴリズムである→到達可能性(有限オートマトン)

ε動作をもつ非決定性有限オートマトンから直接DFAを作るのにも使うことができる

https://gyazo.com/bd6fb30b71b7d1c2b6a4275f434d9582