図は、偶数個の1を含むビット列を受理するオートマトンの状態遷移図であり、二重丸が受理状態を表す。
a、bの正しい組合せはどれか。
a | b | |
ア | 0 | 0 |
イ | 0 | 1 |
ウ | 1 | 0 |
エ | 1 | 1 |
答え ウ
【解説】
1が偶数個の時は“偶”の状態で、奇数個の時は“奇”の状態になるので、“奇”の状態で、1が入力されたときは、“奇”→“偶”に状態が遷移する。(aには1が入る。)
“奇”の状態で、0が入力されても、1の個数に変化がないので、状態は遷移しない。(bには0が入る。)
【キーワード】
・有限オートマトン
・状態遷移表