内容について
有限オートマトンについて勉強したので、自分の理解を深める意味も込めて、読んだ本の中で出てきたオートマトンをElixirで書いてみました。
動作環境
Elixir version : 1.5.2
OS : debian 8 (docker container)
有限オートマトン
まずは有限オートマトンについて軽く定義しておきます。有限オートマトンとは
有限個の状態と遷移と動作の組み合わせからなる数学的に抽象化された「ふるまいのモデル」である。
簡単に言えば、ある状態に対して何かしら入力をすると、別の状態（そのままの状態のこともある）に遷移していく機械ってことです。
有限オートマトンは５つの要素から構成されています。
Q : 状態の有限集合
∑ : アルファベットの有限集合
δ : Q × ∑ -> Q 遷移関数
q0 : 開始状態
F : F ⊆ Q で表される受理状態の集合
上記５つの要素を合わせて
M = (Q, ∑, δ, q0, F)
っと表します。
そして、ある文字列の集合Aがある有限オートマトンMで受理されたなら、Aは機械Mの言語であるといい、MはAを認識するっとも言います。
自動ドア
では、早速有限オートマトンをElixirで作っていきます。
今回勉強した本で、一番最初に出てきた有限オートマトンは自動ドアの有限オートマトンでした。
まずは自動ドアの用語。
---
-------------- | -----------
| | | | |
| フロントパッド | | | リアパッド |
| | | | |
-------------- | -----------
|
---
ドア
フロントパッド : 通過しようとする人の存在を検知するパッド
リアパッド : ドアの後ろにいる人とぶtから内容にするためにドアの反対側に人がいないかを検知するパッド
※ 今回の自動ドアは前後方向に開閉する自動ドアを想定しています（本にそう書いてあったから）。
自動ドアを上記に記述した有限オートマトンの５つの要素に当てはめていきたいと思います。
Q : open(開いてる状態）、close（閉じてる状態）
∑ : front（人がフロントパッドの上にいる）、rear（人がリアパッドの上にいる）、both（フロントとリアの両パッド上に人がいる）、neither（どちらのパッドの上にも人がいない）
q0 : close（本では定義してなかったが、今回はcloseが開始状態とする）
F : open（本では定義してなかったが、今回はopenを受理状態とする）
では、これをElixirで書いていきます。
# 自動ドア
defmodule AutomaticDoor do
def open(:neither) do
:close
end
def open(:front) do
:open
end
def open(:rear) do
:open
end
def open(:both) do
:open
end
def close(:neither) do
:close
end
def close(:front) do
:open
end
def close(:rear) do
:close
end
def close(:both) do
:close
end
end
# 有限オートマトン
defmodule FiniteAutomation do
def q(:open, [head| tail]) do
AutomaticDoor.open(head)
|> q(tail)
end
def q(:close, [head| tail]) do
AutomaticDoor.close(head)
|> q(tail)
end
def q(state, []) do
state
end
end
# 入力される∑の集合
inputs = [:front, :both, :rear, :rear, :front, :neither, :front]
IO.inspect FiniteAutomation.q(:close, inputs)
簡単に解説していくと、AutomaticDoor モジュールでは各自動ドアの状態とそれに対する入力ごとにメソッドを定義していきます。
そして、その入力に対する次の状態を返します。
defmodule FiniteAutomation do
def q(:open, [head| tail]) do
AutomaticDoor.open(head)
|> q(tail)
end
def q(:close, [head| tail]) do
AutomaticDoor.close(head)
|> q(tail)
end
def q(state, []) do
state
end
end
FiniteAutomationモジュールでは、それぞれの状態のパターンごとにメソッドを定義し、入力の集合がなくなるまで再帰処理を繰り返していきます。
とりあず、今回はここまでにしておきます。
次はもう少し複雑になった（予定）有限オートマトンをElixirで書いていきたいと思います。