次の状態遷移図で表現されるオートマトンで受理されるビット列はどれか。
ここで、ビット列は左から順に読み込まれるものとする。
| ア | 0000 | イ | 0111 | ウ | 1010 | エ | 1111 |
答え ウ
【解説】
下図のように各状態にラベルを付けると
状態aから状態bへの遷移は1、状態bから状態cへの遷移は0で、状態bで1でも状態bのまま、状態cになると0でも1でも状態cのままなので、受理されるビット列は“10”を含んだものになるので、1010(ウ)になります。
【キーワード】
・状態遷移図
- 状態遷移図
システムとして複数の状態をもち、事象によりその状態が移る動作(状態遷移)を図にしたものです。
有限オートマトンの図が状態遷移図になります。
また、ソフトウェアの開発では状態遷移図から状態遷移表を作成することもあります。
もっと、「状態遷移図」について調べてみよう。
戻る
一覧へ
次へ