情報に関する理論 (全41問中40問目)
No.40
図は1の数が偶数個のビット列を受理するオートマトンの状態遷移図であり，“偶”と書かれた二重丸が受理状態を表す。a，b の正しい組合せはどれか。
出典：平成17年春期 問11
- [出題歴]
- 応用情報技術者 H25春期 問3
- ソフトウェア開発技術者 H19春期 問7
分類
テクノロジ系 » 基礎理論 » 情報に関する理論
正解
ウ
解説
矢印で表される初期状態から1→aと遷移し受理状態となった場合、1の個数が偶数個となるためにはaが1でなければなりません。したがってaは1になります。
同様に初期状態から1→b→aを遷移し受理状態となった場合、1の個数が偶数個となるためにはbが0でなければなりません。したがってbは0になります。
∴a＝1、b＝0
同様に初期状態から1→b→aを遷移し受理状態となった場合、1の個数が偶数個となるためにはbが0でなければなりません。したがってbは0になります。
∴a＝1、b＝0