部分集合構成法
変換後のDFAの状態数は変換前のNFAに依存する。NFAの状態数が n {\displaystyle n} であるとき、DFAの状態数は最大で 2 n {\displaystyle 2^{n}} となりうる。特に、任意の自然数 n {\displaystyle n} に対して、 n {\displaystyle n} 個の状態からなるNFAであって、変換後のDFAの状態数が 2 n {\displaystyle 2^{n}} である、すなわち初期状態から任意の状態の部分集合に到達可能であるものが存在することが知られており、故に最悪計算量が Θ ( 2 n ) {\displaystyle \Theta (2^{n})} となることが示されている。変換後のDFAの状態数が非常に大きくなる例として、 { 0 , 1 } {\displaystyle \{0,1\}} をアルファベットとし、最後から n {\displaystyle n} 番目の要素が 1 {\displaystyle 1} であるような文字列を受理するオートマトンを考える。これをNFAで構築した場合状態数は n + 1 {\displaystyle n+1} となるが、DFAでは 2 n {\displaystyle 2^{n}} 個の状態を要する。図は n = 4 {\displaystyle n=4} におけるNFAとDFAの状態遷移図である。