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

正解

ウ. 1010

正答率 63.4%（1,641人中 1,040人が正解）

問題の解説

初期状態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で終わり、受理状態に到達しません。