オートマトン/第一類/ミーリー型順序機械

ミーリー型順序機械 (Mealy machine) は機械の出力が状態と入力の組み合わせによって決まる順序機械である。 ミーリー型順序機械は、次に示す 3 つの有限集合 $Q,\mathrm{\Sigma },\mathrm{\Delta }$ と，これらの関係を定める二つの関数 $\delta ,\lambda$ および特定の状態 $q_0$ を指定することにより定まる．

• 状態の有限集合 $Q$
• 入力記号の有限集合 $\mathrm{\Sigma }$
• 出力記号の有限集合 $\mathrm{\Delta }$
• 状態推移関数 (state transition function) $\delta$：機械の現在の状態 $p\in Q$ とそれへの入力 $a\in \mathrm{\Sigma }$ のすべての組み合わせに対して，次の時点の状態 $q\in Q$ を $\delta (p,a)=q$ により一意に定める関数．
• 初期状態 $q_0\in Q$

以上により定まった順序機械 $M$ について，これらをこの順に並べて

$M=(Q,\mathrm{\Sigma },\mathrm{\Delta },\delta ,\lambda ,q_0)$

と形式的に表す．

（例） ミーリー型順序機械 $M_1=(Q_1,{\mathrm{\Sigma }}_1,{\mathrm{\Delta }}_1,{\delta }_1,{\lambda }_1,q_{01})$， ただし $Q_1=\{p,q\},{\mathrm{\Sigma }}_1=\{0,1\},{\mathrm{\Delta }}_1=\{0,1\},{\delta }_1(p,0)=p,{\delta }_1(p,1)=q,{\delta }_1(q,0)=p,$ ${\delta }_1(q,1)=q,{\lambda }_1(p,0)=0,{\lambda }_1(p,1)=0,{\lambda }_1(q,0)=0,{\lambda }_1(q,1)=1,q_{01}=p$．

状態推移表 (state transision table)

ミーリー型順序機械の内容を見やすく表現するための表で，前述の順序機械 $M_1$ に対しては次のようになる．

現在の状態		次の状態		出力
		入力		入力
		0	1	0	1
⇒	p	p	q	0	0
	q	p	q	0	1

ここで初期状態は「現在の状態」の欄の中で矢印「⇒」で指し示して明示し，通常は「現在の状態」の最初の行に置く． $\delta (p,a)=q,\lambda (p,a)=b$(例では $a=0,1,b=0,1$） であるとき，現在の状態が $p$ である行と入力 $a$ の交点の「次の状態」欄には状態 $q$ を置き，「出力欄」には $b$ を記入する．

状態推移図 (state transition diagram)

順序機械の動作を図式的に表現することによって，見やすくかつ把握しやすくしたのが状態推移図である。先の順序機械 $M_1$ に対しては 図3 のようになる。

図3

状態遷移図において、各々の状態は状態を示す記号を丸で囲ったもので表し，特に初期状態には矢印をつけて明示する。 また $\delta (p,a)=q,\lambda (p,a)=b$ であるとき，状態 p から状態 q へ向かう推移を示す矢印を引き，それぞれの矢印には入出力を表すラベル $a/b$ をつける．

プログラミング演習問題(1)

ミーリー型順序機械を定義する記述法①を各自考案し、①と入力記号列②を与えたときの順序機械の出力を出力するプログラムを作成せよ。