NFAを実装するSchemeコード - 算術の夢の楽園

どうもAaronです。

またSchemeでおもちゃ作ってたので紹介記事を書きます。

NFA(非決定型有限状態オートマトン)を生成するプログラムです。

主題とは関係ありませんがこれがわかってないと自分でオートマトンをデザインできないのでほんの少しだけ触れます(なおSchemeについての解説ではないので今回関係がある部分のみです。)

Schemeではプログラム中に’(クオート)に続けて「外部表現」と呼ばれる表現を書くことでScheme内部のデータ構造を人間にとって視覚的な表示で入力することができます(これはSchemeの意味論にとって正確な物言いとは言えないかもしれないが)。

そのなかでも今回使う引数の形式に対応する外部表現は以下のようになります。

(<object1> <object2> <object3> …)(object1,object2,object3,...は他の外部表現)

object1,object2,object3,...からなる「リスト」の外部表現です。

(<object1> . <object2>)(object1,object2は他の外部表現)

object1とobject2のペアの外部表現です。

"string"

「string」という文字列の外部表現です。

#\γ(γはSchemeが認識可能な一文字)

「γ」という文字の外部表現です。

あとはRepl.itの下のほうにある僕のサンプル見ながら慣れてください。

(抽象構文)

(create-automata State-Set Initial-States Transition Accept-States)

(説明)

日本語版wikipediaの「非決定性有限オートマトン」の記事で導入された定義を参照することにします。

ここでcreate-automata関数は以下のようなオートマトンをエミュレートする手続きを生成します。

以下特に定義なく用いた記号や用語はwikipediaの当該記事で使われているものを指します。

(以下create-automata関数の入力仕様及び実現されるオートマトンの仕様)

$\Sigma$ (入力文字集合):Schemeが読み取れる文字のうち、" $\$$ "を除くすべて。勿論必要に応じてその適当なsubsetだと勝手に考えることは自由である。

$\rm S$ (状態集合):第一引数で与える「文字列のリスト」を状態集合として用いる。

$\rm S_0$ (初期状態集合):第二引数で与える。また唯一wikipediaの定義と今回の実装がわずかにずれているところ。この実装は複数の初期状態があることを許しているため、初期状態をリストの形式で受け取る。

$\rm T$ (遷移関数):第三引数で与える。「「「「読み込む文字」と「現在の状態」のペア」と「遷移先の文字」のペア」のリスト」という形式で受け取る。

$\rm A$ (受理状態):第四引数で与える。形式は $\rm S$ や $\rm S_0$ と同じである。

なお空文字列の記号として $\epsilon$ はIDEへの入力が面倒くさいため、代わりに $\$$ を用いた。

(以上)

前述の通り出力は手続きである。仮にtest-automataと呼ぶことにする。

test-automataは文字列一つを引数に取り、標準出力に「「上記のオートマトン」に「引数の文字列」を読ませた場合の操作的意味論」をエミュレートする。