HOME»ソフトウェア開発技術者平成19年春期»午前問7
ソフトウェア開発技術者平成19年春期 午前問7
問7
図は，偶数個の1を含むビット列を受理するオートマトンの状態遷移図であり，二重丸が受理状態を表す。a，bの正しい組合せはどれか。
分類 :
テクノロジ系 » 基礎理論 » 情報に関する理論
正解 :
ウ
解説 :
矢印で表される初期状態から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