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

automata-libライブラリを使うと、Pythonで簡単にオートマトンを実装できます。

この記事でやること

Pythonで決定性有限オートマトンを利用して、2進数が3で割りきれるかどうかの判定を行います。よく教科書に載っている例題ですね。
入力が3の倍数であれば受理され、そうでなければ拒否されます。
状態遷移図にするとこんな感じです。

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

環境

OS

• Pengwin 1.4.1 on WSL

Pythonバージョン

Python 3.8.1

使うライブラリ

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クラスを利用します。

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進数の文字列であることに注意。　

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

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

受理される例

>>> for i in modulo.read_input_stepwise('110'):
...   print(i)
...
q0
q1
q0
q0

拒否される例

>>> 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