正答3
解説
正解は3です。
図のオートマトンは、左の初期状態(太矢印)、中央の状態、右の受理状態(二重丸)の3状態です。
初期状態は0で自分に戻り、1で中央の状態へ進みます。
中央の状態は1で自分に戻り、0で受理状態へ進みます。
受理状態は0でも1でも自分に戻ります。
読み終えたときに受理状態にいるビット列が受理されます。
【選択肢別解説】
1:× 0000は、初期状態で0を読むたびに自分に戻るだけです。
最後まで初期状態にいるので受理されません。
2:× 0111は、0で初期状態にとどまり、1で中央へ進み、残りの1でも中央にとどまります。
受理状態に到達しないので受理されません。
3:○ 1010は、1で中央へ、0で受理状態へ進みます。
その後の1と0では受理状態にとどまるので、受理されます。
4:× 1111は、最初の1で中央へ進んだ後、1を読むたびに中央にとどまります。
0が来ないので受理状態に進めません。
【ポイント】
このオートマトンは「1の後に0が現れる」部分を含むビット列を受理します。
状態遷移図の問題は、選択肢のビット列を1文字ずつたどるのが確実です。