状態の集合を Q、入力記号の集合を Σ、空動作を ε とするとき、空動作を含む非決定性有限オートマトンの遷移関数 δ の型として適切なものはどれか。ここで、$2^Q$ は Q の部分集合全体の集合を表す。

解説

正解は「$Q\times (\Sigma \cup \{\epsilon \})\to 2^Q$」です。空動作を含む NFA では、現在の状態と「入力記号または ε（入力を読まない動作）」の組に対して、次の状態の候補が0個以上あり得るので、遷移先は状態の集合（Q の部分集合）になります。「$Q\times \Sigma \to Q$」は、遷移先がちょうど1つに決まる DFA の遷移関数の型です。「$Q\times \Sigma \to 2^Q$」は空動作を含まない NFA の型で、ε による遷移を表せません。「$Q\to \Sigma \times Q$」は、入力を読まずに記号を出力するような形で、入力を受理するオートマトンの遷移関数になっていません。