DFA の最小化において、2つの状態 p と q を1つの状態にまとめてよい条件として、適切なものはどれか。

解説

正解は「どの入力記号列を与えても、受理するかどうかの結果が p と q で一致する」です。このとき p と q は等価（区別不能）であり、まとめても受理する言語は変わりません。実際には、まず受理状態と非受理状態を区別し、ある入力記号で区別済みの組へ遷移する状態の組を順に区別していき、最後まで区別されなかった状態をまとめます。「p と q が、同じ入力記号で互いに遷移し合う」だけでは、その後の受理の結果が一致するとは限りません。「p と q が、どちらも非受理状態である」ことは必要条件にすぎません。「p と q に入ってくる遷移の数が等しい」ことは、等価性と関係ありません。