順序機械
入力と出力のあるシステムを考えるよ。
入力に応じてシステム状態が変わっていくシステムを順序機械というよ。
順序機械は、システムがとりうる状態の集合 、システムが受け取る入力の集合 、システムが行う出力の集合 、どの状態のときにどんな入力があると次はどの状態になるかを定める状態推移関数(状態遷移関数) 、どういう条件でどういう出力をするかを定める出力関数 、初期状態 が決まると、一意に決まるよ。
ただし、出力関数の決め方によって、順序機械はミーリー型とムーア型に区別できるよ。
つまり、状態推移関数と同じように、この状態でこの入力があったらこの出力だ、というように出力を決める(つまり関数の定義域が直積 )のがミーリー型で、入力は関係なく、この状態のときには必ずこの出力だと決める(つまり定義域が )のがムーア型だよ。
ミーリー型で、つまり入力と推移前の状態によって次の状態での出力が決まる、というように記述してはいるけど、実際には入力値にかかわりなく出力が各状態で一定の場合には、出力関数から入力引数を省略することでムーア型にすることができるよ。この逆をするとムーア型からミーリー型にすることができるよ。
あと、ある状態について入力値ごとに出力値が違うときも、この出力値ごとに状態が違うんだと考えてやれば、やっぱりムーア型にすることができるよ。
あと、入力値と出力値の組み合わせが同じ二つの状態は、互いに等価だというよ。等価な状態同士を同じ状態と考えると、記述を簡単化することができるよ。