基本情報技術者試験のサンプル問題を解こう！（4）（科目A）「状態遷移図」

基本情報技術者試験のサンプル問題（科目A）を解いてみよう。

今回のテーマは、「状態遷移図」である。

問４
入力記号，出力記号の集合が｛0，1｝であり，状態遷移図で示されるオートマトンがある。0011001110 を入力記号とした場合の出力記号はどれか。ここで，入力記号は左から順に読み込まれるものとする。また，S1 は初期状態を表し，遷移の矢印のラベルは，入力／出力を表している。

ア　 0001000110
イ　 0001001110
ウ　 0010001000
エ　 0011111110

この問題では、オートマトンの状態遷移図を使って、入力記号列 0011001110 に対応する出力記号列を求めることが求められている。

1. オートマトンの基本構造

• 状態：S1（初期状態）、S2、S3
• 入力／出力関係
  • S1 → S1（入力 0 → 出力 0）
  • S1 → S2（入力 1 → 出力 0）
  • S2 → S1（入力 0 → 出力 0）
  • S2 → S3（入力 1 → 出力 1）
  • S3 → S1（入力 0 → 出力 0）
  • S3 → S3（入力 1 → 出力 1）

2. 入力記号列の処理

入力記号「0011001110」を左から順に処理し、出力記号を決定する。

ステップごとの状態変化と出力

1. 初期状態は S1
   • 入力 0 → S1 → 出力 0
   • 入力 0 → S1 → 出力 0
   • 入力 1 → S2 → 出力 0
   • 入力 1 → S3 → 出力 1
   • 入力 0 → S1 → 出力 0
   • 入力 0 → S1 → 出力 0
   • 入力 1 → S2 → 出力 0
   • 入力 1 → S3 → 出力 1
   • 入力 1 → S3 → 出力 1
   • 入力 0 → S1 → 出力 0

出力記号列は 0001000110 となる。

3. 正解の選択肢

この出力記号列と選択肢を照らし合わせると 「ア」 が正解になる。