修了試験 2021-01-24実施分 基本情報技術者試験 問5

解説

正解は3です。 このオートマトンは、これまでに読んだ1の個数が偶数か奇数かを状態として覚えます。 図では、初期状態かつ受理状態（二重丸）が「偶」です。 「偶」には0で自分に戻るループがあり、「偶」から「奇」へは1で遷移しています。 「奇」から「偶」へ戻る矢印がa、「奇」の自己ループがbです。 【状態遷移の考え方】 「奇」の状態で1を読むと、1の個数は偶数になるので「偶」へ戻る必要があります。 したがって、a＝1です。 「奇」の状態で0を読んでも、1の個数は変わらないので「奇」に留まります。 したがって、b＝0です。 【選択肢別解説】 1：× a＝0では、0を読んだだけで「偶」に戻ってしまいます。 1の個数が奇数のまま受理されるので誤りです。 2：× a＝0、b＝1は、0と1の役割が完全に逆です。 1を読んでも「奇」に留まり、偶奇を正しく数えられません。 3：○ a＝1で「奇」から「偶」へ戻り、b＝0で「奇」に留まります。 1を読むたびに偶奇が反転し、正しく受理できます。 4：× b＝1とすると、「奇」から1で遷移する先が2つになり、決定性の遷移になりません。 0を読んだときの遷移先も定まりません。 【ポイント】 偶奇を数えるオートマトンは「1で状態が入れ替わり、0では状態が変わらない」という形になります。 図の「偶」側の遷移と対称になるように「奇」側を決めると覚えやすいです。