問題プレビューID: a288d00e基本情報技術者試験 午前免除試験 2010年7月

問 4
基本情報技術者試験 午前免除試験 2010年7月

図で表される有限オートマトンで受理される文字列はどれか。ここで,初期状態は左端の太い矢印で示された状態,受理状態は二重丸で示されている。

図の有限オートマトンの状態遷移は次のとおりである。初期状態を q0q_0,受理状態を q3q_3 とする。

  • q0q_0:0 で q0q_0 へ(自己ループ),1 で q1q_1 へ
  • q1q_1:0 で q0q_0 へ,1 で q2q_2 へ
  • q2q_2:0 で q0q_0 へ,1 で q3q_3 へ
  • q3q_3:0 で q0q_0 へ,1 で q4q_4 へ
  • q4q_4:0 でも 1 でも q4q_4 へ(自己ループ)
解説

正解は「ウ」です。

初期状態 q0q_0 から文字を1つずつ読み,受理状態 q3q_3 で入力が終われば受理されます。各選択肢を追跡すると次のようになります。

  • ア 01011:q0→q0→q1→q0→q1→q2q_0 \to q_0 \to q_1 \to q_0 \to q_1 \to q_2 となり,q2q_2 で終わるので不受理です。
  • イ 01111:q0→q0→q1→q2→q3→q4q_0 \to q_0 \to q_1 \to q_2 \to q_3 \to q_4 となり,q4q_4 で終わるので不受理です。
  • ウ 10111:q0→q1→q0→q1→q2→q3q_0 \to q_1 \to q_0 \to q_1 \to q_2 \to q_3 となり,q3q_3 で終わるので受理されます。
  • エ 11110:q0→q1→q2→q3→q4→q4q_0 \to q_1 \to q_2 \to q_3 \to q_4 \to q_4 となり,q4q_4 で終わるので不受理です。

したがって,正解は「ウ」です。

関連問題

本文が同じ・似ている問題を表示しています