応用情報技術者 2014年 春期 午前2 問04

末尾110の受理状態【午前2解説】

正解の理由

解法ステップ

1. 状態ごとの遷移動作を確認する（表から各状態の 0・1 に対する遷移先を読む）。
   • a: 0→a、1→b
   • b: 0→c、1→d
   • c: 0→a、1→b
   • d: 0→c、1→d
2. 末尾3ビットが110となる典型的な遷移を追う（左から読む）。
   • …1 → …11 → …110 に対応する遷移は a → b → d → c
3. 任意に長い文字列でも「最後の3ビットが110である」場合は最後の3入力だけを見れば上の遷移に従い状態に到達することを確認する。
4. よって受理状態として状態（選択肢ウ）を選べば良い。

選択肢別の誤答解説

• ア: a
  a は 0 を読み続けると自己ループするなど「直近が0寄り」の状態であり、末尾が110 のときに常に到達する状態ではありません。例えば 110 を読むと a → b → d → c となり a では終わりません。
• イ: b
  b は「最後に1を読んだ直後」を表す役割を持つ遷移先で、末尾が110 の最終状態ではありません（110 の最後では 0 を読んで c に移るため）。
• ウ: c
  末尾が …110 となると最終的に c に到達するため正解です。したがって受理状態はになります。
• エ: d
  d は「直近が11 となっている」ことを示す状態で、110 の最後には d → 0 によって c に遷移するため、最終受理状態としては不適切です。

よくある誤解

• 「最後の2ビットが10であれば良いから c は正しいが、10 の場合も受理されるのではないか」
  末尾3ビットの判定では「最後に 0 を読んだ直前の状態」が重要です。設問のオートマトンの遷移構造では、…110 の場合に限って最終的に c に到達するようになっているため、単純に「最後の2ビットだけを見ればよい」という短絡は危険です。
• 「d を受理状態にすればよいのではないか」
  d は 11 を保持する状態であり、110 のときは d から 0 を受けて c に移るため、d を受理にすると 111 など 11 で終わる文字列を誤って受理する可能性があります。

補足コラム

• この種の問題は「接尾辞（suffix）検出」を行う有限オートマトンの理解に直結します。固定長 m の末尾パターンを検出する最小の DFA は通常 m+1 個の状態を持ち、各状態は「現在までに一致しているパターンの最長接頭辞の長さ」に対応します。今回のパターン「110」（長さ 3）に対して 4 状態を用意している点はその典型です。
• KMP（Knuth–Morris–Pratt）法の部分一致の考え方と同様に、各状態は「どれだけパターン先頭に一致しているか」を表現しており、それを遷移表で実装したのが今回の表の考え方と整合します。

FAQ