改訂新版 世界大百科事典 「状態遷移図」の意味・わかりやすい解説
状態遷移図 (じょうたいせんいず)
state transition diagram
通常は（有限）オートマトンの動作を表現するために用いられる図をいう。オートマトンは，ある状態qにいるとき，入力記号xを受けとるとf（q，x）なる状態に遷移する。同時にg（q，x）なる出力記号を出す。出力がこのように状態と入力の関数のときミーリーMealy型といい，状態のみの関数のときムーアMoore型という。オートマトンの動作は状態遷移関数fと出力関数gを，例えば表の形で，与えれば決まるが，これを図示したものが状態遷移図である。すなわち各状態qに対してそれぞれ1個の節点nodeを定め，f（q，x）＝q′およびg（q，x）＝yなら節点qから節点q′へラベルx/yのついた辺edgeを描く。ムーア型の場合はf（q，x）＝q′，g（q）＝yのとき，節点qから節点q′へラベルxのついた辺を描き，節点qには出力記号yを記入する。図は，0と1からなる入力系列を入れて，1の個数が3の倍数になるたびに出力1を出すオートマトンの状態遷移図である。状態遷移図はまた，有限マルコフ連鎖を図示するために各辺に遷移確率を記入したものとして用いることがある。
執筆者：西尾 英之助
出典 株式会社平凡社「改訂新版 世界大百科事典」改訂新版 世界大百科事典について 情報