有限オートマトン

外部からの逐次的入力(sequential input)に対して状態を変え,何らかの応答を出力するシステムをモデル化したものを有限オートマトンといいます.

有限オートマトンは順序機械(Sequential Machines)とも言われます.

現在の状態 $q_{0}$ に入力 $a$ が入ると,状態 $q_{2}$ となって出力が $b$ となるように,出力が入力と状態に依存する順序機械をミーリー型順序機械(Mealy Machine)といいます.\[\begin{xy}\xymatrix{&*++[o][F-]{q_0} \ar@(ur,ul)_1 \ar[r]^{a/b} & *++[o][F-]{q_1} \ar@(ur,ul)_1}\end{xy}\]

現在の状態 $q_{0}$ に,入力 $a$ が入ると,次の状態 $q_{1}$ となるというように,出力が現在の状態のみの関数になっている順序機械をムーア型順序機械(Moore Machine)といいます.\[\begin{xy}\xymatrix{&*++[o][F-]{q_0/b} \ar@(ur,ul)_1 \ar[r]^{a} & *++[o][F-]{q_1/c} \ar@(ur,ul)_1}\end{xy}\]

$Q$ を状態の空ではない有限集合,$\Sigma$ を入力記号の集合($a \in \Sigma$),$\delta$ を状態遷移関数,$q_{0} \in Q$ を初期状態,$F \subset Q$ は受理状態の集合とすると,有限オートマトンは,\[M = (Q,\Sigma,\delta,q_{0},F)\]と表されます.


#:アメリカの数学者であり計算機科学者のGeorge H. Mealy(1927-2010)に由来します.

参照:

Vita brevis, ars longa. Omnia vincit Amor.





















確率測度の拡張 還元可能性 reducibility オートマトン 言語 反射律 reflexivity rule 真偽値 truth value