平成28年度 春期 午前 問2

✓ これが正解ウ1010

解説

1010は2文字目で受理状態に入り、そのまま留まるので受理されます。

オートマトンは、開始の状態から入力ビットを1つずつ読み込み、遷移表に従って状態を移動します。読み終えたときにいる状態が受理状態のとき、そのビット列は受理されたと言います。設問の遷移表を追うと、この機械は最初に1を受け取って中央の状態へ進み、そこで0を受け取って初めて右端の受理状態へ入ります。受理状態は自己ループなので、そのあとは0でも1でも同じ状態に留まります。判定の軸は、途中で1が現れたあとに0が続く箇所が1度でもあるかどうかです。この条件を1度でも満たすビット列は受理状態に入り、以降は何を読んでも受理を保つので、読み終えたときに右端に居ることができます。ここで扱っているのは、状態遷移で言語を認識する有限オートマトンの考え方です。

ほかの選択肢はなぜ違うのか

• ア0000：0が4回続くビット列を挙げています。開始状態は0で自己ループするので、状態が動かないまま読み終わります。中央の状態へも受理状態へも到達しないため、読み終わりの状態が開始のままで、受理には至りませんでした。
• イ0111：0の後に1が3回続くビット列を挙げています。最初の0で開始のまま留まり、続く1で中央へ進みます。以後は1が続くので中央で自己ループし、0を受け取る機会がないまま読み終わり、受理状態には入れませんでした。
• エ1111：1だけが4回続くビット列を挙げています。最初の1で中央の状態へ進みますが、そのあとは1が続くだけで中央の自己ループを回り、0が現れないため右端の受理状態へ移る機会がありませんでした。