入力記号、出力記号の集合が {0,1} であり、状態遷移図で示されるオートマトンがある。0011001110 を入力記号とした場合の出力記号はどれか。ここで、入力記号は左から順に読み込まれるものとする。また、S1は初期状態を表し、遷移の矢印のラベルは、入力/出力を表している。
[状態遷移図]
出典基本情報技術者試験 サンプル問題 科目A 問4
ア
0001000110
イ
0001001110
ウ
0010001000
エ
0011111110
状態遷移図とオートマトン
正解は ア （0001000110）です。 初期状態S1から、入力記号を一つずつ読みながら遷移先と出力を追跡します。 入力記号「 0011001110 」を左から1文字ずつ読み込み、遷移先と「出力記号」をメモしていきましょう。 入力 現在の状態 次の状態 出力 0 S1 S1 0 0 S1 S1 0 1 S1 S2 0 1 S2 S3 1 0 S3 S1 0 0 S1 S1 0 1 S1 S2 0 1 S2 S3 1 1 S3 S3 1 0 S3 S1 0 これらをすべて繋げると「0001000110」となります。 以上から、得られる出力列は「0001000110」です。