Elixirで有限オートマトンの仕組みを少し理解する。その②

## 内容について

前回、有限オートマトンとはどういうものかと、それについて簡単ではありましたがElixirで有限オートマトンを実装しました。
今回はもう少し様々な有限オートマトンの実装を行います。

[Elixirで有限オートマトンの仕組みを少し理解する。その①](https://qiita.com/kobatako/items/166b8a31b91703f836a6)

## 動作環境

Elixir version : 1.5.2
OS : debian 8 (docker container)

## 有限オートマトン

### 0と1で受理されるかどうかの判定

今回実装した有限オートマトンは0と1からなる文字列から、それが受理されるかどうかの判定を行う有限オートマトンになります。
今回実装した有限オートマトンの定義は下記になります。

> Q : {q1, q2, q3}
∑ : {1, 0}
δ : transition関数
開始状態 : q1
F : q2

実際のプログラムになります。

```
defmodule State do
    def transition(:q1, 1) do
        :q2
    end
    def transition(:q1, 0) do
        :q1
    end
    def transition(:q2, 1) do
        :q2
    end
    def transition(:q2, 0) do
        :q3
    end
    def transition(:q3, 1) do
        :q2
    end
    def transition(:q3, 0) do
        :q2
    end

    def isAccept?(state) do
        state in [:q2]
    end
end

defmodule FiniteAutomation do
    def q(state, [head | tail]) do
        State.transition(state, head)
        |> q(tail)
    end
    def q(state, []) do
        State.isAccept?(state)
    end
end

alphabet = [0, 0, 1, 1, 0, 1, 0, 0, 0]
IO.inspect FiniteAutomation.q(:q1, alphabet)
```

この有限オートマトンが受理されるAの定義は下記のようになります。

> A = {w|wは少なくとも一つの１を含み、かつ、再鬼現れる１の後ろに偶数個の０を含む｝

このような入力を受け取るとこの有限オートマトンは受理されることになります。

ではプログラムを細かく見ていきたいと思います。

```
alphabet = [0, 0, 1, 1, 0, 1, 0, 0, 0]
IO.inspect FiniteAutomation.q(:q1, alphabet)
```
FiniteAutomation.q(:q1, alphabet)のq1は最初の状態となり、alphabetは実際の入力値となります。

```
defmodule FiniteAutomation do
    def q(state, [head | tail]) do
        State.transition(state, head)
        |> q(tail)
    end
    def q(state, []) do
        State.isAccept?(state)
    end
end
```
ここで入力された値から先頭のものをひとつずつ取り出し、現在の状態と先頭の入力値から次の状態を受け取り、配列が空になるまで繰り返されます。
そして、配列が空になったときの状態が受理状態かどうか判定します。

```
defmodule State do
    def transition(:q1, 1) do
        :q2
    end
    def transition(:q1, 0) do
        :q1
    end
    def transition(:q2, 1) do
        :q2
    end
    def transition(:q2, 0) do
        :q3
    end
    def transition(:q3, 1) do
        :q2
    end
    def transition(:q3, 0) do
        :q2
    end

    def isAccept?(state) do
        state in [:q2]
    end
end
```
現在の状態と入力値で次の状態を決定しているモジュールになります。ここのtransitionが有限オートマトンの定義であったδになります。
isAcept?内の[:q2]は受理状態のリストになります。

### 先頭文字と末文字との有限オートマトン

入力した文字列で先頭の文字と終わりの文字が同じのものを受理する有限オートマトンになります。

まずは、有限オートマトンの定義から

> Q : {s, q1, q2, r1, r2}
∑ : {a, b}
δ : transition関数
開始状態 : s
F : q1, r1

では、プログラムを載せます。

```
defmodule State do
    # 開始状態
    def transition(:s, :a) do
        :q1
    end
    def transition(:s, :b) do
        :r1
    end

    # Q側の状態遷移
    def transition(:q1, :a) do
        :q1
    end
    def transition(:q1, :b) do
        :q2
    end
    def transition(:q2, :a) do
        :q1
    end
    def transition(:q2, :b) do
        :q2
    end

    # R側の状態遷移
    def transition(:r1, :a) do
        :r2
    end
    def transition(:r1, :b) do
        :r1
    end
    def transition(:r2, :a) do
        :r2
    end
    def transition(:r2, :b) do
        :r1
    end

    def isAccept?(state) do
        state in [:q1, :r1]
    end
end

defmodule FiniteAutomation do
    def q(state, [head | tail]) do
        State.transition(state, head)
        |> q(tail)
    end
    def q(state, []) do
        State.isAccept?(state)
    end
end

alphabet = [:a, :b, :a, :b, :b, :b, :a]
IO.inspect FiniteAutomation.q(:s, alphabet)
```

今回の有限オートマトンでは、最初の文字を受け取った段階で状態のqかr、どちらに状態が遷移するか判定します。
先頭の文字が、aであればqのほうへ。
先頭の文字が、bで張ればrのほうへ遷移します。
そのあとは、各qとrで状態を遷移し先頭の文字と同じ文字が来たタイミングで受理の状態へ遷移します。

こうすることで簡単に、文字の先頭と最後の文字を判定する有限オートマトンができました。

## 最後に

今回は少ない入力の集合のみ（例えば、aとbのみ）で有限オートマトンを作りました。
もちろん複数の入力の集合を受け取る有限オートマトンもありますんで、次回はそれを実装しようと思います。
また、有限オートマトンの設計も軽く触れればいいです。