情報に関する理論 (全53問中27問目)
No.27
図は，偶数個の1を含むビット列を受理するオートマトンの状態遷移図であり，二重丸が受理状態を表す。a，bの正しい組合せはどれか。
出典：平成25年春期 問3
- [出題歴]
- 基本情報技術者 H17春期 問11
- ソフトウェア開発技術者 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