【基本・応用情報技術者】オートマトンと状態遷移図
スポンサーリンク
こんにちは。たろすです。
今回はオートマトンと状態遷移図について説明します。
オートマトンとは
オートマトンは一定の規則に従って複数の内部状態の間を遷移する仮想的な機械で、現在の状態と入力の組み合わせを規則の中から探し出し、指定された次の状態へ遷移する。規則に該当する組み合わせがなければ同じ状態を維持する。規則は状態遷移表や状態遷移図として書き表すことができる。
オートマトン（状態機械）とは - IT用語辞典 e-Words
つまり、現在の状態にある入力を与えると特定の状態へ遷移する機械のことです。
オートマトンの問題では状態遷移図がよく使われます。
状態遷移図の読み方
次のような状態遷移図があります。
丸が状態で、矢印が遷移、矢印の横にある値が入力を表しています。
まず最初に確認するのが初期状態と終了状態です。
なにもないところから矢印が入ってきているq0が初期状態、二重丸のq2が終了状態です。
問題としては選択肢としてビット列が与えられて、「次の状態遷移図で表現されるオートマトンで受理されるビット列はどれか」などと問われます。
「受理される」とは入力をすべて入れたときに終了状態になるものを指します。
具体的な読み方は例題を解きながら見ていきましょう。
例題
次の状態遷移図で表現されるオートマトンで受理されるビット列はどれか。
ア．00100
イ．10110
ウ．11110
エ．00111
ア（00100）の解説
初期状態はq0です。
アの最初の入力は0なのでq1に移ります。
次の入力も0なので自己遷移します。
次の入力は1なのでq2に遷移します。
ここで終了状態に到達しましたが、入力がまだあるので続きます。
次の入力は0なのでq0に遷移します。
さらに次の入力も0なのでq1に遷移します。
すべての入力を終えて到達した状態はq1なのでアのビット列は受理されません。
イ（10110）の解説
解き方はアと同様なので詳しい解説は省略します。
ウ（11110）の解説
解き方はアと同様なので詳しい解説は省略します。
エ（00111）の解説
解き方はアと同様なので詳しい解説は省略します。
最後に到達した状態が終了状態となりました。
したがって答えはエになります。
