部分集合構成法
初期状態が複数存在するNFAに対しては以下の2つの対処が考えられる。
初期状態全てからなる集合を考え、これに対応するDFAでの状態を初期状態とする。
変換しようとするNFAがε-遷移を許すならば、新たに状態を1つ加えてこれを初期状態とし、元の初期状態それぞれへε-遷移できるように遷移規則を書き換える。
DFA最小化に関するBrzozowskiのアルゴリズムは内部で部分集合構成法を用いる。具体的には、まず与えられたDFAの遷移規則全てを逆向きにし、また初期状態と受理状態を入れ替えることにより、元のDFAが受理する全ての文字列の逆順をちょうど受理するNFAを得る。次にこのNFAに対して部分集合構成法を適用して等価なDFAへと変換する。この手続きをもう一度繰り返すことにより、元のDFAと等価でかつ状態数最小のDFAが得られる。このアルゴリズムは前述の通り部分集合構成法を用いるため、その最悪計算量は指数オーダーとなる。
上で示したアルゴリズムにより任意のNFAに対し等価なDFAを構成できることが分かった。一方で任意のDFAに対してもそれと等価なNFAを構築することができる。すなわち、DFA ( Q , Σ , δ , q 0 , F ) {\displaystyle (Q,\Sigma ,\delta ,q_{0},F)} に対しては、 δ ′ ( q , a ) = { δ ( q , a ) } {\displaystyle \delta '(q,a)=\{\delta (q,a)\}} を用いたNFA ( Q , Σ , δ ′ , q 0 , F ) {\displaystyle (Q,\Sigma ,\delta ',q_{0},F)} を考えれば良い。これにより、ある言語が正規であることと、あるNFAによって認識されることが同値であることが示される。