(非)決定性有限オートマトンがチューリングマシンより真に弱い計算能力を持つというのはどのオートマトンの教科書にも書いてあることです。このことが意味するのは、オートマトンでできることは全てチューリングマシンでできるということです。ということでチューリングマシンである普通のコンピューターでオートマトンを動かすプログラムをpythonで書きました。3か月間オートマトンについての講義を受け、その期末試験の直後にプログラムを書き始めたので、驚くほど簡単に書けました。
オートマトンがこのように定義されているということから、DFAを表現するクラスが保持すべき情報がこれだけだと判断しました。もちろんどうにかして情報を圧縮したり分かりやすいようにまとめ直すことも可能だとは思いましたが、形式的定義が十分わかりやすいと思ったので自分でどうにかするのはやめました。
オートマトンの形式的定義では に関する縛りは何もありません。このことが意味するのは、 の中身が文字列だろうと整数だろうと関数だろうと関係が無く、ただ区別ができて集合に属しているかチェックできるものならば何でもいい、ということです。
プログラムでも同じ方針を取り、 を"任意の要素の集合"として表現しました。pythonはもともと動的型付けなので、 の要素が任意であることを明示する必要はありません。また要素の集合を表現するには組み込みのsetクラスを利用できます。
以下に の一例を示します。ここでは状態を表すのに自然数を使っています。
これは簡単でした。文字の集合を表せばよいので、 と同じように組み込みのsetクラスを利用しました。
「遷移関数」という名前からpythonの関数を使って表現してもいいのではないかと思いましたが、そうしてしまうとオートマトンに本来できない計算が遷移関数の中で行われてしまう可能性があったのでやめにしました。
オートマトンが持つ唯一の機能である、文字列を受け取ってそれを受理するか拒否するかを決める処理について書きます。
文字列を一文字ずつ読み込み、そのたびごとに状態を遷移させ、最後の文字を読んだときの状態が終状態に含まれるか否かで受理するか拒否するかを決めます。データ構造をきちんと決めてしまえばこの処理を書くのは楽でした。
これを実行すると以下のような出力が得られ、正しく動作していることが確かめられます。