応用情報技術者試験 応用情報技術者試験 平成28年度秋期 午前 問4: 表は，入力記号の集合が {0, 1}，状態集合が {a, b, c, d} である有限オートマトンの状態遷移表である。長さ 3 以上の任意のビット列を左（上位ビ

正解

ウ. c

正答率 40.1%（1,249人中 501人が正解）

問題の解説

この遷移表は、直前に読んだ 2 ビットを状態として覚えている (a が 00、b が 01、c が 10、d が 11)。110 で終わる列は、最後の 2 ビットが必ず 10 なので、読み終えると状態 c にいる。したがって、c を受理状態にすれば 110 で終わる列を漏れなく受理できる。

選択肢ごとの解説

• ア状態 a は直前の 2 ビットが 00 の状態である。110 で終わる列の最後の 2 ビットは 10 なので、a では終わらない。
• イ状態 b は直前の 2 ビットが 01 の状態で、最後に読んだのは 1 である。110 の最後のビットは 0 なので、b では終わらない。
• ウ正しい。状態 c は直前の 2 ビットが 10 の状態で、例えば a から 110 を読むと、b、d を経て c に着く。
• エ状態 d は直前の 2 ビットが 11 の状態である。110 の最後の 0 を読むと d から c へ遷移するので、読み終えた時点では d ではなく c にいる。