平成28年度 春期 基本情報技術者試験 午前 問2

解説

この状態遷移図は，開始状態で0が続く間はそこにとどまり，1が来ると中間状態に移り，中間状態で1が続く間はとどまり，0が来ると受理状態（二重丸）に達する仕組みを表しています。受理状態に一度達すると，その後は0でも1でも受理状態にとどまり続けます。つまり，ビット列の中で「1の後に0が続く」箇所が現れれば受理されます。

選択肢ごとの解説

• ア誤り。1が一度も現れないため中間状態に進むことができず，受理状態に到達しません。
• イ誤り。0の後1が3回続いて中間状態にとどまりますが，その後0が現れないため受理状態に到達しません。
• ウ正しい。最初の1で中間状態に移り，続く0で受理状態に達し，残りの1，0は受理状態のループで読み込まれるため受理されます。
• エ誤り。1が続く間は中間状態のループにとどまり続け，0が一度も現れないため受理状態に到達しません。