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

選択肢

• ア0001000110
• イ0001001110
• ウ0010001000
• エ0011111110

正解と解説

正解：ア 0001000110

初期状態から入力を1文字ずつ読み、遷移のラベルに従って出力を並べる。出力が1になるのは、1が2つ以上続いて第3の状態へ入った後だけで、それ以外の遷移はすべて0を出力する。入力を順にたどると、2組目の1の位置と、その後に1が3つ続く箇所の2文字目以降で1が現れ、出力は0001000110となる。

選択肢ごとの解説

• ア各遷移をたどった結果と一致する正しい出力列。
• イ後半の1の並びで出力される1の個数が実際より多い。
• ウ1が出る位置が実際の遷移とずれている。
• エ入力をそのまま写したような列で、遷移による出力になっていない。

同じ分野の他の問題

• 入力されたビットに対して出力されるビットが0か1のいずれかである確率を遷移確率という。遷移確率を表にしたとき，a，b，c…2026年度 公開問題 科目A 問1
• 液晶ディスプレイなどの表示装置において、傾いた直線の境界を滑らかに表示する手法はどれか。2024年度 公開問題 科目A 問6
• 3次元グラフィックス処理におけるクリッピングの説明はどれか。2023年度 公開問題 科目A 問5
• 次のBNFで定義される＜変数名＞に合致するものはどれか。 ＜数字＞::=0｜1｜2｜3｜4｜5｜6｜7｜8｜9 ＜英字＞…2019年度 秋期 午前 問7
• Random(n)は、0以上n未満の整数を一様な確率で返す関数である。整数型の変数A、B及びCに対して次の一連の手続を実…2019年度 秋期 午前 問6