応用情報技術者 2013年春期午前2 問03

問題文

図は、偶数個の1を含むビット列を受理するオートマトンの状態遷移図であり、二重丸が受理状態を表す。a, bの適切な組合せはどれか。

選択肢

ア：

イ：

ウ：（正解）

エ：

偶数個の1を含むビット列を受理するオートマトン【午前2 解説】

要点まとめ

結論：a=1、b=0の組合せ（選択肢ウ）が正解です。
根拠：状態「偶」は偶数個の1を受理し、「奇」は奇数個の1を表し、1の入力で状態が切り替わるためa=1、b=0となります。
差がつくポイント：0の入力は状態を変えず、1の入力で「偶」と「奇」が相互に遷移することを正確に理解できるかが鍵です。

正解の理由

状態「偶」は偶数個の1を含むビット列を受理し、自己ループの入力が0であるため、0を読み込んでも状態は変わりません。一方、「偶」から「奇」へ遷移するのは1の入力です。
「奇」状態の自己ループはbで表され、ここでbは0か1かを判断します。1の入力で「奇」から「偶」へ戻る遷移がaで示されているため、a=1、b=0が正しい組合せとなります。
したがって、選択肢ウ（a=1、b=0）が正解です。

よくある誤解

「偶」と「奇」の状態遷移で、0の入力でも状態が変わると誤解しやすいです。0は状態を変えず、1だけが状態を切り替えるトリガーである点を押さえましょう。

解法ステップ

状態「偶」が偶数個の1を受理し、二重丸で示されていることを確認する。
「偶」から「奇」へは1の入力で遷移し、「偶」には0の自己ループがあることを理解する。
「奇」状態の自己ループがbで示されているため、bが0か1かを考える。
「奇」から「偶」へはaの入力で遷移し、1の入力で戻ることからa=1と判断する。
以上よりa=1、b=0の組合せを選択する。

選択肢別の誤答解説

ア（a=0、b=0）：a=0は「奇」から「偶」へ1で戻る遷移と矛盾し、誤り。
イ（a=0、b=1）：a=0は誤り、b=1は「奇」状態の自己ループが1であることを示すが、状態遷移図と合わない。
ウ（a=1、b=0）：正解。1の入力で状態が切り替わり、0の入力で状態が維持される。
エ（a=1、b=1）：b=1は「奇」状態の自己ループが1であることを示し、状態遷移図と矛盾する。

補足コラム

この問題はパリティ検査の基本的なオートマトン設計に関するものです。偶数個の1を数えるオートマトンは、状態数が2つで十分であり、入力1で状態を切り替え、入力0で状態を維持する特徴があります。これにより、ビット列のパリティ判定が効率的に行えます。

FAQ

Q: なぜ0の入力で状態が変わらないのですか？
A: 0は1の個数に影響を与えないため、パリティ状態は変わらず自己ループとなります。

Q: 状態「奇」と「偶」はどのように区別しますか？
A: 「偶」は偶数個の1を含む状態で受理状態、「奇」は奇数個の1を含む状態で非受理状態です。

関連キーワード: オートマトン、状態遷移、パリティ検査、偶数個の1, 受理状態、ビット列解析

← 前の問題へ次の問題へ →

\ せっかくなら /

応用情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！

応用情報技術者 2013年 春期 午前2 問03

問題文

選択肢