基本情報技術者試験 - 令和7年1月修了 - 問3

答え ： ウ
分野 ： テクノロジ系 › 基礎理論 › 基礎理論 › 情報に関する理論
解説 ：
「有限オートマトン」という，入力された記号の並びに応じて状態が次々と移り変わっていく仕組みについての理解を問う問題です。有限オートマトンは，コンパイラの文字列解析など情報科学の基礎理論でよく使われる考え方です。今回は状態a・b・c・dがあり，0または1のビットを1つ読み込むたびに表に従って状態が変化します。

問題文の条件は「読み込んだビット列の末尾（一番最後）が110で終わっている」ものを受理する，つまり正しいと判定することです。状態遷移表を使って，110というビット列を最後に読んだときにどの状態にたどり着くかを確認すると，状態cにたどり着くことが分かります。例えば，状態aから0，1，0の順に進むとa→a→b→cとなり，最終的にcで終わります。受理状態としてcを設定すればよいので，正解は「ウ」です。他の選択肢の状態を受理状態にすると，末尾が110でない別のビット列も誤って受理してしまう，あるいは110で終わるビット列を受理できないため，いずれも不正解です。