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