平成26年度 高度共通 午前I（PM試験） 問2

正解：ウ

AI解説

正解はウ(状態c)。有限オートマトンの各状態は「直前までに読んだ入力の末尾パターン」を記憶する役割をもつ。受理条件は末尾が110であることなので、初期状態から1→1→0と遷移をたどり、110を読み終えた時点で到達する状態を状態遷移表で確認すると状態cになる。したがってcを受理状態とすればよい。 ア: 状態aは末尾が110となった状態ではなく、別の入力パターン(例えば0が続いた状態)に対応するため受理状態にできない。 イ: 状態bは末尾が1で終わるなど、110完成前の途中状態に対応するため不適切である。 ウ: 正解。遷移表で1,1,0の順に入力をたどると到達するのが状態cであり、末尾110を読み終えた状態を表す。 エ: 状態dは末尾110以外のパターンに対応する状態であり、これを受理すると110で終わらない列も受理してしまう。 💡 この型の問題は「受理したいパターンをそのまま初期状態から入力してみて、到達した状態が答え」という解法で機械的に解ける。長い列でも末尾3文字分の遷移だけ追えばよい。