トップ その他 ITスキル体系 情報の基礎理論 情報の理論 状態遷移

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

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

状態遷移図とは

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

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

状態遷移表とは

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

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

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

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

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

オートマンとは

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

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

有限オートマンとは

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

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

状態遷移表の例

入力信号の検査の例

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

状態

信号


S1


S2


S3


S4
t1S3
t2S3S2
t3S4S1
t4S1S2

ここで、初期状態を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とし、文字列の検査しています。

文字列
空白数字符号小数点その他





a
b
c
d
a
a
e
a
b
b
b
e
c
e
e
e
d
d
d
e
e
e
e
e
文字列
空白数字符号小数点その他





a
b③⑤
c
d
a
a
e
a
b
b
b
e
c
e
e
e
d
d
d
e
e
e
e
e

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

戻る

サイト内のページ

言語
C・C++ /HTML /Java /JavaScript /PHP /シェルスクリプト

開発環境
Ant /Eclipse /gcc /gdb /g++ /JDK /JUnit /ZAP

技術・仕様
Ajax /CORBA /Java EE(旧称J2EE) /JNI

ライブラリ/Framework/CMS
jQuery /Lucene /MyBatis /Spring /Struts /Seasar2 /WordPress

ITインフラ OSとミドルウェア
Linux /Windows /シェル
Apache/Tomcat /MySQL /Redis /Solr /vsftpd

ITインフラ PC 製品
ZOTAC

ITインフラ サーバー
Web公開サーバー構築

ITインフラ ネットワーク
プログラミング /機器 /構築

ITインフラ セキュリティ
公開サーバーのセキュリティ

SI
ホームページの作り方 /小さな会社のISMS

その他
IT用語 /ITスキル体系 /トレンド履歴

スポンサーリンク

関連サイト内検索ツール

zealseedsおよび関連サイト内のページが検索できます。

IPアドレス確認ツール

あなたのグローバルIPアドレスは以下です。

34.203.213.116

HTMLの表示色確認ツール

パスワード生成ツール

文字数のプルダウンを選択して、取得ボタンを押すと「a~z、A~Z、0~9」の文字を ランダムに組み合わせた文字列が表示されます。

ここに生成されます。

スポンサーリンク