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

正解：ウ

AI解説

有限オートマトンで「最後が110で終わるビット列を受理する」には、直前までの入力の末尾が110となった時点で到達している状態を受理状態とすればよい。初期状態から1→1→0と読み込んだときの遷移を状態遷移表で順にたどると状態cに到達するため、cを受理状態とすれば末尾が110の列だけが受理される。状態遷移表を実際にたどって確認するのが確実な解法である。 ア: 状態aは末尾が110となる入力列で到達する状態ではないため、受理状態にすると誤った列を受理してしまう。 イ: 状態bは末尾のパターンが110と一致しない状態(例えば末尾が1や11の状態)であり、受理状態として不適切である。 ウ: 正しい。初期状態から110と読み込んだとき(および任意の列の末尾が110のとき)に到達する状態がcであるため、cを受理状態とすればよい。 エ: 状態dは末尾が110以外のパターンに対応する状態であり、受理状態にすると条件を満たさない列も受理される。 💡 オートマトン問題は「各状態が『末尾がどんなパターンか』を記憶している」と捉える。具体的な短い入力例(110、0110など)を遷移表でたどり、到達状態を確認するのが最速の解法。