有限オートマトンを実装してなんとなく挙動をつかむ

前置き

みなさんは、チューリングテストに合格していますか？

本題

有限オートマトンとは、内部状態を持ち、入力によってさまざまな状態に遷移し動作する機械を抽象化したものです。

これは、有限オートマトン - Wikipediaから引用した図です。このように、状態を表す図形と矢印を使った状態遷移図や、状態遷移表によって表されることが多いです。

さて、しばしば私たちは有限オートマトンをペンで書き下ろすのですが、それがどのように振る舞うのか、逐一入力を変えて確かめてみたくなります。しかしそれは大変な苦痛を伴います。 そのようなときには実装してしまいましょう。

gist.github.com

コンストラクタに、アルファベットの集合(ここでは 01 のどちらか)と、状態遷移表に対応する辞書型のリストを渡します。

{'0': 0, '1': 1, 'accepted': True}

は、この状態にあるとき0を入力として受け取ったら状態0に、1のときは状態1に遷移し、受理状態であることを表しています。

gyazo.com

上のコードの例にある有限オートマトンの状態遷移図です。受理状態にあるとき、fa.accepted() は True を返します。

% python finite_automata.py
0 0 True
1 1 False
2 10 False
3 11 True
4 100 False
5 101 True
6 110 True
7 111 False
8 1000 False
9 1001 True
10 1010 True
11 1011 False
12 1100 True
13 1101 False
14 1110 False
15 1111 True
16 10000 False
17 10001 True
18 10010 True
19 10011 False
20 10100 True
21 10101 False
22 10110 False
23 10111 True
24 11000 True
25 11001 False
26 11010 False
27 11011 True
28 11100 False
29 11101 True
30 11110 True

こうして私は、2進数で3の倍数になる文字列かどうかを判定する有限オートマトンを書いたつもりでいて、じつは書けてなかったことを理解することができました。よかったですね。

今後の展望

• graphviz で状態遷移図を生成できるように、dot言語に変換する機能