問題4
次の表は、入力記号の集合が{0, 1}、状態集合が{a, b, c, d}である有限オートマトンの状態遷移表である。 長さ3以上の任意のビット列を左(上位ビット)から順に読み込んで最後が110で終わっているものを受理するには、どの状態を受理状態とすればよいか。
| ア | a |
| イ | b |
| ウ | c |
| エ | d |
解答・解説を見る
解答：ウ
入力によって様々な動作をするシステム(仕組み)をモデル化したものをオートマンという。また有限の状態を持ち現在の状態と入力から出力と次の状態を決めて動作するものを特に有限オートマンという。
有限オートマンには、開始と終了の時の状態が決まっており、最後の入力で終了するときの状態を受理状態という。
- 110の左端の1を読み込む：状態がa又はcの時はb、bまたはdの時はdに遷移する
- 110の中央の1を読み込む：状態がb又はdの時に1を読み込むとdに遷移する
- 110の右端の0を読み込む：状態がdの時に0を読み込むとcに遷移する
したがって、ウが正解である。