平成26年度春期 応用情報技術者試験 午前 問4

正解：ウ

AI解説

この有限オートマトンは、入力ビット列の末尾が「110」で終わるかどうかを、直前まで読んだ記号列がパターン「110」のどこまで一致しているか(接頭辞の一致長)を状態として保持しながら判定する構成になっている。状態遷移表をたどると、記号列の末尾がちょうど「110」で終わった直後に到達する状態がcであり、この状態を受理状態とすれば「最後が110で終わる」任意のビット列を過不足なく受理できる。 ア: aは初期状態、あるいはパターンとまだ一致していない状態に相当し、ここで受理すると「110」で終わらない文字列まで誤って受理してしまう。 イ: bは「1」までは一致したがまだ「110」の途中である状態に相当し、この状態で受理すると末尾が「110」で終わっていない文字列も受理してしまう。 ウ: 正しい。状態遷移表上、直前の3記号が「110」で終わったときにちょうど到達する状態がcであり、これを受理状態とすれば条件を満たす文字列だけを受理できる。 エ: dを受理状態にすると、状態遷移表の構造上、末尾が「110」以外で終わる文字列を受理してしまう、または「110」で終わる文字列を取りこぼしてしまい、条件と一致しない。 💡 「文字列が特定のパターンで終わるかどうか」を判定するオートマトンは、状態を「パターンとどこまで一致したか」の進捗として設計するのが定石。表を読むときは、パターンの各記号を1文字ずつ与えたときにどの状態へ遷移するかを追跡すると受理状態を特定しやすい。