応用情報技術者 2009年 春期 午前2 問03

有限オートマトンの受理入力列判定【午前2 解説】

要点まとめ

• 結論：入力列「1101」が初期状態$S_1$から受理状態$S_3$へ遷移し受理される。
• 根拠：状態遷移図の矢印とラベルに従い、各文字で状態を追うと$S_3$で終了するのは「1101」のみ。
• 差がつくポイント：自ループや双方向遷移の理解と、受理状態で入力列が終わるかの確認が重要。

正解の理由

• $S_1$（初期）で「1」を読み、$S_2$へ移動（$S_1\stackrel{1}{\to }{S}_2$）
• $S_2$で「1」を読み、$S_1$へ戻る（$S_2\stackrel{1}{\to }{S}_1$）
• $S_1$で「0」を読み、$S_3$へ移動（$S_1\stackrel{0}{\to }{S}_3$）
• $S_3$で「1」を読み、自ループで$S_3$に留まる（$S_3\stackrel{1}{\to }{S}_3$）
  最終状態が受理状態$S_3$であるため、この入力列は受理されます。

よくある誤解

解法ステップ

1. 初期状態$S_1$からスタートする。
2. 入力列の各文字を順に読み、状態遷移図の矢印に従って状態を移動する。
3. 最後の文字を読み終えた時点での状態が受理状態$S_3$か確認する。
4. 受理状態ならその入力列は受理される。そうでなければ不受理。

選択肢別の誤答解説

• ア: 1011
  $S_1\stackrel{1}{\to }{S}_2\stackrel{0}{\to }{S}_2\stackrel{1}{\to }{S}_1\stackrel{1}{\to }{S}_2$で終了し、$S_2$は非受理状態。
• イ: 1100
  $S_1\stackrel{1}{\to }{S}_2\stackrel{1}{\to }{S}_1\stackrel{0}{\to }{S}_3\stackrel{0}{\to }{S}_2$で終了し、$S_2$は非受理状態。
• ウ: 1101
  最終状態が$S_3$で受理される。
• エ: 1110
  $S_1\stackrel{1}{\to }{S}_2\stackrel{1}{\to }{S}_1\stackrel{1}{\to }{S}_2\stackrel{0}{\to }{S}_2$で終了し、$S_2$は非受理状態。

補足コラム

FAQ