基本情報技術者試験 - 令和8年1月修了 - 問3
表は，入力記号の集合が { 0，1 }，状態集合が { a，b，c，d } である有限オートマトンの状態遷移表である。長さ3以上の任意のビット列を左（上位ビット）から順に読み込んで最後が 110 で終わっているものを受理するには，どの状態を受理状態とすればよいか。
| 0 | 1 | |
| a | a | b |
| b | c | d |
| c | a | b |
| d | c | d |
| ア | a |
|---|---|
| イ | b |
| ウ | c |
| エ | d |
答え ： ウ
分野 ： テクノロジ系 › 基礎理論 › 基礎理論 › 情報に関する理論
解説 ：
有限オートマトンの状態遷移表を読み取り，特定の条件（末尾が「110」で終わる）を満たすビット列を受理する状態を見つける問題です。状態遷移表は，各状態で0または1を読んだときにどの状態へ移るかを示しています。この問題を解くコツは，それぞれの状態が「これまで読んだビット列の末尾のパターン」を表していると考えることです。
表を追いながら，「1」を読んで「1」を読んで「0」を読む，という一連の遷移をたどると，最終的にたどり着く状態が受理状態になります。実際に状態aから始めて0や1を色々な順序で入力し，110で終わる場合にどの状態に到達するかを地道に確認すると，状態cにたどり着くことが分かります。誤りの選択肢a，b，dは，途中の遷移や他のビットパターンで到達してしまう状態であり，末尾が110で終わるという条件を満たさないケースも含まれてしまいます。
分野 ： テクノロジ系 › 基礎理論 › 基礎理論 › 情報に関する理論
解説 ：
有限オートマトンの状態遷移表を読み取り，特定の条件（末尾が「110」で終わる）を満たすビット列を受理する状態を見つける問題です。状態遷移表は，各状態で0または1を読んだときにどの状態へ移るかを示しています。この問題を解くコツは，それぞれの状態が「これまで読んだビット列の末尾のパターン」を表していると考えることです。
表を追いながら，「1」を読んで「1」を読んで「0」を読む，という一連の遷移をたどると，最終的にたどり着く状態が受理状態になります。実際に状態aから始めて0や1を色々な順序で入力し，110で終わる場合にどの状態に到達するかを地道に確認すると，状態cにたどり着くことが分かります。誤りの選択肢a，b，dは，途中の遷移や他のビットパターンで到達してしまう状態であり，末尾が110で終わるという条件を満たさないケースも含まれてしまいます。
共有ボタンをタップ