基本情報技術者試験 基本情報技術者試験 平成28年度 春期 午前 午前 問2: 次の状態遷移図で表現されるオートマトンで受理されるビット列はどれか。ここで，ビット列は左から順に読み込まれるものとする。

問題本文

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

選択肢

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

正解

ウ. 1010

解説

初期状態S0で0は自己ループ、1でS1へ。S1で1は自己ループ、0で受理状態S2へ。S2は0,1とも自己ループ。受理されるには途中で『1の後に0』が出現する必要があります。

選択肢ごとの解説

• ア.0000はS0で自己ループのまま受理状態S2に到達せず受理されません。
• イ.0111はS0→S0→S1→S1→S1で終わり、受理状態に到達しません。
• ウ.1010はS0→S1(1)→S2(0)→…で受理状態に到達し以降も受理状態のまま、受理されます。
• エ.1111はS0→S1→S1→S1→S1で終わり、受理状態に到達しません。