Pythonで決定性有限オートマトンを実装して、3の倍数を判定する

automata-libライブラリを使うと、Pythonで簡単にオートマトンを実装できます。
# この記事でやること
Pythonで決定性有限オートマトンを利用して、2進数が3で割りきれるかどうかの判定を行います。よく教科書に載っている例題ですね。
入力が3の倍数であれば受理され、そうでなければ拒否されます。
状態遷移図にするとこんな感じです。
![mod3dfa.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/19807/553e19e2-974c-919b-53d3-b7a681627425.png)

大学の宿題であれば自分で実装した方がいいと思いますが、ここではautomata-libライブラリで実装します。

# 環境
## OS
- [Pengwin 1.4.1](https://www.whitewaterfoundry.com/) on WSL

## Pythonバージョン
Python 3.8.1

## 使うライブラリ
[automata-lib](https://pypi.org/project/automata-lib/)
automata-libはPython3.4以上で動作します。

# 環境の構築
環境はpipenvで構築しました。

```
$ pipenv --python 3.8
$ pipenv install automata-lib
$ pipenv shell
```

# 実行例
第一引数で入力の数値（10進数）を与えます。3で割り切れる（受理される）場合は`Result: Accepted`、3で割り切れない（拒否される）場合は`Result: Rejected`と出力されます。そのあとに遷移も出力されます。便利ですね。
## 受理される例

```
$ ./modulo_three.py 12
12
Result: Accepted
Transitions
q0
q1
q0
q0
q0
```

## 拒否される例

```
$ ./modulo_three.py 11
11
Result: Rejected
Transitions
q0
q1
q2
q2
q2
Traceback (most recent call last):
  File "./modulo_three.py", line 40, in <module>
    for i in modulo.read_input_stepwise(entry):
  File "/home/***/.local/share/virtualenvs/qiita-modulo_three-AeTt0v42/lib/python3.8/site-packages/automata/fa/dfa.py", line 
105, in read_input_stepwise
    self._check_for_input_rejection(current_state)
  File "/home/***/.local/share/virtualenvs/qiita-modulo_three-AeTt0v42/lib/python3.8/site-packages/automata/fa/dfa.py", line 
87, in _check_for_input_rejection
    raise exceptions.RejectionException(
automata.base.exceptions.RejectionException: the DFA stopped on a non-final state (q2)
```

# 説明
## オートマトンの定義
決定性有限オートマトンの実装はDFAクラスを利用します。

```python:modulo_three.py
modulo = DFA(
    states = {'q0', 'q1', 'q2'},
    input_symbols = {'0', '1'},
    transitions = {
        'q0': {'0': 'q0', '1': 'q1'},
        'q1': {'0': 'q2', '1': 'q0'},
        'q2': {'0': 'q1', '1': 'q2'}
    },
    initial_state='q0',
    final_states={'q0'}
)
```

- `state`でこのオートマトンの状態を定義します。
- `input_symbols`で入力シンボルを定義します。
- `transitions`で各状態から別の状態に遷移するルールを定義します。たとえば`q0`を例にすると、入力が0なら`q0`に遷移、入力が1なら`q1`に遷移します。
- `initial_state`で開始状態を指定します。
- `final_state`で受理状態を指定します。

## オートマトンの実行
単純に受理されるか判定する場合は、`accept_input`メソッドを使います。受理される場合は　`True`、拒否される場合は`False`を返します。`accept_input`メソッドの引数は2進数の文字列であることに注意。　

```python
>>> modulo.accepts_input('10')
False
>>> modulo.accepts_input('110')
True
```

どのように遷移するのか見たいときは、`read_input_stepwise`メソッドを使います。このメソッドは遷移をジェネレータで返します。拒否される場合は`RejectionException`例外を返します。

```python:受理される例
>>> for i in modulo.read_input_stepwise('110'):
...   print(i)
...
q0
q1
q0
q0
```

```python:拒否される例
>>> for i in modulo.read_input_stepwise('10'):
...   print(i)
... 
q0
q1
q2
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/home/***/.local/share/virtualenvs/qiita-modulo_three-AeTt0v42/lib/python3.8/site-packages/automata/fa/dfa.py", line 
105, in read_input_stepwise
    self._check_for_input_rejection(current_state)
  File "/home/***/.local/share/virtualenvs/qiita-modulo_three-AeTt0v42/lib/python3.8/site-packages/automata/fa/dfa.py", line 
87, in _check_for_input_rejection
    raise exceptions.RejectionException(
automata.base.exceptions.RejectionException: the DFA stopped on a non-final state (q2)
```

# コード
ここに置いてあります。MITライセンスです。
https://github.com/bateleurX/qiita-modulo_three