順序機械とは
それまでの入力で、出力が決まる
a(t-k)，...，a(t-2)，a(t-1) → b(t)
k ＝ ∞ の時：無限順序機械
k ≠ ∞ の時：有限順序機械
Ｍ = (Ｑ，煤CΔ，δ，λ，ｑ
0
)
Ｑ：状態の有限集合
Σ：入力記号の有限集合
Δ：出力記号の有限集合
δ：状態遷移関数
∃
p∈Ｑ，
∃
a∈Σ，
∃
q∈Ｑ ⇒ δ(p，a) = q
λ：出力関数
∃
p∈Ｑ，
∃
a∈Σ，
∃
b∈Δ ⇒ λ(p，a) = b ←
Mealy Machine（ミーリー型）
∃
p∈Ｑ，
∃
b∈Δ ⇒ λ(p) = b ←
Moore Machine（ムーア型）
ｑ
0
：初期状態
ミーリー型
出力が入力と状態に依存する。
現在の状態 p に、入力 a が入ると、次の状態 q になって、出力が b となる
状態遷移図（state transition diagram）
入力：
入力列：
出力列：
状態遷移表
現在
の
状態
次の状態
出力
入力
入力
0
1
0
1
⇒p
p
q
0
0
q
p
q
0
1
δ：Ｑ×Σ→Ｑ，λ：Ｑ×Σ→Δ
Ｑ = { p, q }，Σ = { 0, 1 }，Δ = { 0, 1 }
ムーア型
出力が現状態のみの関数になっている。
現在の状態 p に、入力 a が入ると、次の状態 q になる
状態遷移図（state transition diagram）
入力：
入力列：
出力列：
状態遷移表
現在
の
状態
次の状態
出力
入力
0
1
⇒r
r
s
0
s
r
t
0
t
r
t
1
δ：Ｑ×Σ→Ｑ，λ：Ｑ→Δ
Ｑ = { r, s, t }，Σ = { 0, 1 }，Δ = { 0, 1 }
状態遷移図（state transition diagram）の例（ミーリー型）
電灯のスイッチ
ON（点灯）とOFF（消灯）の二つのボタンを持つ電灯
ボタン：
自動販売機
１００円玉と５０円玉のみを受け付け、１５０円のペットボトル入りのお茶、単品を販売する自動販売機
コイン：
取出口：
戻る
