図は、偶数個の1を含むビット列を受理するオートマトンの状態遷移図であり、二重丸が受理状態を表す。
a、bの正しい組合せはどれか。
| a | b | |
| ア | 0 | 0 |
| イ | 0 | 1 |
| ウ | 1 | 0 |
| エ | 1 | 1 |
答え ウ
【解説】
1が偶数個の時は“偶”の状態で、奇数個の時は“奇”の状態になるので、“奇”の状態で、1が入力されたときは、“奇”→“偶”に状態が遷移する。(aには1が入る。)
“奇”の状態で、0が入力されても、1の個数に変化がないので、状態は遷移しない。(bには0が入る。)
【キーワード】
・有限オートマトン
・状態遷移表
- 有限オートマトン
有限個の状態と有限個の事象からなるものの動作を表現するもの。
通常は状態遷移図で表されることが多い。
状態遷移図では状態を○状態の遷移を→で表し、事象は→の添え字で記述する。 - 状態遷移表
有限オートマトンを表現するのに表を用いたもので、各状態についての各事象の動作をすべて記述することが可能である。
制御系のソフトウェア開発では、状態遷移表を書いて設計を行うことが多い。
状態遷移表を書くためのツールもある。
もっと、「有限オートマトン」について調べてみよう。
戻る
一覧へ
次へ