状態遷移―状態遷移とは？から図、表、オートマトンや書き方の例など

状態遷移とは、ある状態から他の状態へ変わること。状態遷移図と表、オートマトンや書き方の具体例など状態遷移について説明しています。

▲記事トップへ

状態遷移図とは

状態遷移図とは、状態の移り変わりを図で表したものです。 時間の経過や事象の発生に基づいて記述していきます。

状態遷移図は、表形式で表す場合もあります。

状態遷移表とは

状態遷移表は現在の状態と与えられた条件により次の状態を求めるための表です。

現在の状態である表の縦軸と、与えられた条件である横軸の交点を次の状態とします。

Status Tigger tableとも呼ばれ、状態(Status)と条件(Tigger)によって状態の遷移のルールを表しています。

オートマトンと有限オートマトン

実は、状態遷移表は、有限オートマトンの遷移関数 T を記述した表なのです。

オートマトンとは

オートマトンは、コンピュータそのものを数学的観点からモデル化し、 問題解決のための処理手順を定式化したものです。

入力とそのときの状態によって出力が決定される機械をモデル化したものです。 つまり、オートマトンは、出力が入力だけでなく過去の入力によって決まる機械です。

有限オートマトンとは

オートマトンのうち、最も単純なモデルを有限オートマトンといいます。

有限オートマトンで覚えておきたいのは、有限オートマトンには「受理」と「非受理」という言葉があることです。 入力が終了したときの状態が受理状態にあれば「受理する」といい、それ以外であれば「受理しない」といいます。

状態遷移表の例

入力信号の検査の例

次の状態遷移表をもつシステムの状態がS1であるときに、 入力信号（t1、t2、t3、t4、t1、t2、t3、t4）を順次入力したとき、最後の状態をしらべます。 なお、、空欄は状態が変化しないことします。

ここで、初期状態をS1として（t1、t2、t3、t4、t1、t2、t3、t4）の信号が入力されると状態は次のように変化します。
(S1+t1)＝S1⇒(S1+t2)＝S3⇒(S3+t3)＝S4⇒(S4+t4)＝S2⇒
(S2+t1)＝S3⇒(S3+t2)＝S2⇒(S2+t3)＝S2⇒(S2+t4)＝S1

文字列の検査の例）

下の表は、文字列を検査するための状態遷移表です。 検査では、「12.2」について、初期状態aとし、文字列の検査しています。

知識の幅を広げるための参考

• 情報の基礎理論

  基本情報の参考書のお供に！テキスト本＋α！をテーマに数値表現・データ表現、情報の理論など情報の基礎理論についてまとめています。 参考書はあるけど、ここだけ足りないという方にお勧めです！

戻る