次の状態遷移図で表現されるオートマトンで受理されるビット列はどれか。ここで，ビット列は左から順に読み込まれるものとする。

選択肢

• ア0000
• イ0111
• ウ1010
• エ1111

正解と解説

正解：ウ 1010

この状態遷移図は、初期状態で0を読み飛ばし、1が現れると次の状態へ移り、そこで1が続く限りとどまり、0を読んだ時点で受理状態に入って以降は何が来ても受理状態のままという構造になっている。つまり受理される列は「0が0個以上→1が1個以上→0→任意の列」という形である。この形にあてはまるのは1010で、1で第2状態へ移り、続く0で受理状態に達し、残りの10はそのまま受理状態を回る。

選択肢ごとの解説

• ア1が一度も現れないので初期状態から先へ進めず、受理状態に到達しない。
• イ先頭の0は初期状態の自己ループで読み飛ばされ、その後の111は第2状態にとどまるだけで受理状態へ移れない。
• ウ正解。1で第2状態へ移り、次の0で受理状態に入り、残りは受理状態を自己ループする。
• エ1が続く間は第2状態にとどまり、0が一度も現れないため受理状態へ遷移できない。

同じ分野の他の問題

• 入力されたビットに対して出力されるビットが0か1のいずれかである確率を遷移確率という。遷移確率を表にしたとき，a，b，c…2026年度 公開問題 科目A 問1
• 液晶ディスプレイなどの表示装置において、傾いた直線の境界を滑らかに表示する手法はどれか。2024年度 公開問題 科目A 問6
• 3次元グラフィックス処理におけるクリッピングの説明はどれか。2023年度 公開問題 科目A 問5
• 入力記号、出力記号の集合が{0, 1}であり、状態遷移図で示されるオートマトンがある。0011001110を入力記号とし…2022年度 公開問題 科目A 問4
• 次のBNFで定義される＜変数名＞に合致するものはどれか。 ＜数字＞::=0｜1｜2｜3｜4｜5｜6｜7｜8｜9 ＜英字＞…2019年度 秋期 午前 問7