状態数がそれぞれ m と n の2つの DFA があるとき、両方が受理する文字列（共通部分）だけを受理する DFA を直積構成で作ると、状態数はいくつになるか。

解説

正解は「$mn$」です。直積構成では、2つの DFA を同時に動かし、それぞれの現在の状態の組 (p, q) を新しい DFA の1つの状態とします。組の数は m×n 通りなので、状態数は $mn$ です。入力記号ごとに両方の DFA を1ステップずつ進め、両方が受理状態である組を受理状態にすれば共通部分を、少なくとも一方が受理状態である組を受理状態にすれば和を受理できます。「$m+n$」は2つの DFA を並べただけの数で、両者の状態を同時に覚えられません。「$2^{m+n}$」は、NFA を部分集合構成法で決定化する場合の上限に近い形で、直積には不要です。「$\max (m,n)$」でも、2つの DFA の状態を同時に覚えられません。