状態数が n の NFA を部分集合構成法で DFA に変換するとき、得られる DFA の状態数の上限はどれか。

解説

正解は「$2^n$」です。部分集合構成法では、NFA が同時にとり得る状態の集合を DFA の1つの状態とします。n 個の状態からなる集合の部分集合は空集合も含めて $2^n$ 個あるので、DFA の状態数は最大 $2^n$ です。実際には開始状態から到達できる部分集合だけを作ればよく、多くの場合ははるかに少なく済みます。ただし、「末尾から k 番目の記号が a」という言語のように、最小の DFA でも約 $2^k$ 個の状態が必要な例があります。「$n$」は状態数が増えない場合で、一般には成り立ちません。「$n^2$」は、2つの DFA の直積で共通部分を受理するときの状態数に近い値です。「$n!$」は状態の並べ方の数で、部分集合の数ではありません。