Ⅲ－５
下図の決定性有限オートマトンが0100を受理するために、破線で囲まれたア、イ、ウ、エの遷移に割り当てるべき入力の最も適切な組合せはどれか。ただし、二重丸で表現された状態は受理状態を表すものとする。
ア イ ウ エ
① 1 0 1 0
② 1 0 0 1
③ 1 0 0 0
④ 0 1 1 0
⑤ 0 1 0 1
正解
④
解説
① 0100を入力すると、図の右上の状態に遷移する。
② 0100を入力すると、図の下の状態に遷移する。
③ ウとエに同じ値が入ることはない。
④ 正しい。
⑤ 0100を入力すると、図の右上の状態に遷移する。