情報処理安全確保支援士試験の公開問題
2014 春 午前I 問02
このページはIPA Advancedが運営する非公式の学習用ページです。IPAとの提携・公認を示すものではありません。
問題文
表は，入力記号の集合が {0，1}，状態集合が {a，b，c，d} である有限オートマトンの状態遷移表である。長さ 3 以上の任意のビット列を左（上位ビット）から順に読み込んで最後が 110 で終わっているものを受理するには，どの状態を受理状態とすればよいか。
選択肢
- ア: a
- イ: b
- ウ: c
- エ: d
解説の要点
添付の公式解答表では，問2の正解はウ。状態遷移表は添付の公式問題ページを参照する。受理状態は，入力全体を読み終えた時点の状態で判断する。末尾の 110 に注目すると，最初の 1 で b または d，次の 1 で必ず d，最後の 0 で c に移る。末尾より前の入力によらず c に到達するので，受理状態は c となる。
異なる入力列を状態遷移表で追跡し、その経路を比較するには、どのように記録すればよいでしょうか。
関連する問題一覧
公式出典
訂正・編集方針
解説にはAIによる補助生成を含む場合があります。公式の問題冊子・解答例・採点講評を優先し、誤りは確認後に訂正します。