平凡社 世界大百科事典

状態遷移図

通常は(有限)オートマトンの動作を表現するために用いられる図をいう。オートマトンは,ある状態qにいるとき,入力記号xを受けとるとfqx)なる状態に遷移する。同時にgqx)なる出力記号を出す。出力がこのように状態と入力の関数のときミーリーMealy型といい,状態のみの関数のときムーアMoore型という。オートマトンの動作は状態遷移関数fと出力関数gを,例えば表の形で,与えれば決まるが,これを図示したものが状態遷移図である。すなわち各状態qに対してそれぞれ1個の節点nodeを定め,fqx)=q′およびgqx)=yなら節点qから節点q′へラベルx/yのついた辺edgeを描く。ムーア型の場合はfqx)=q′,gq)=yのとき,節点qから節点q′へラベルxのついた辺を描き,節点qには出力記号yを記入する。図は,0と1からなる入力系列を入れて,1の個数が3の倍数になるたびに出力1を出すオートマトンの状態遷移図である。状態遷移図はまた,有限マルコフ連鎖を図示するために各辺に遷移確率を記入したものとして用いることがある。

西尾 英之助
図-状態遷移図
図-状態遷移図