平成25年度 春期 応用情報技術者試験 午前 問3
テクノロジ／基礎理論図は，偶数個の1を含むビット列を受理するオートマトンの状態遷移図であり，二重丸が受理状態を表す。a，bの適切な組合せはどれか。 （注：本サイトでは原問題の表を文字表記に変換しています）
出典：平成25年度 春期 応用情報技術者試験 午前 問3
- アa＝0，b＝0
- イa＝0，b＝1
- ウa＝1，b＝0
- エa＝1，b＝1
正解：ウ
解説
このオートマトンは，これまでに読んだ1の個数の偶奇を状態（偶／奇）として保持します。状態が奇のとき0を読んでも偶奇は変わらないため自己遷移（b）となり，1を読むと偶奇が反転して偶へ戻る（a）必要があります。したがってa＝1，b＝0が正解です。
選択肢ごとの解説
- ア誤り。a＝0，b＝0では，奇状態で1を読んでも偶に戻れず，正しく偶数個の1を判定できません。
- イ誤り。a＝0，b＝1では，奇状態で0を読むと偶に遷移してしまい，1の個数の偶奇と状態が対応しなくなります。
- ウ正しい。奇状態で1を読むと偶奇が反転して偶に戻るのでa＝1，0を読んでも偶奇は変わらず自己遷移するのでb＝0です。
- エ誤り。a＝1，b＝1では，奇状態で0を読んでも偶に遷移してしまい，1の個数の偶奇と状態が対応しなくなります。