直接なにかの書籍に関係するということもないけれど、先日オートマトンについて考えたので、忘れないうちに関連することを二つ書いておこう。
本当の有限ってやつを見せてやりますよ
無限については多くの人が語っているが、有限について語る人はそれに比べれば多くない。希少価値を狙おう。
有限オートマトンの有限は、まさに本当の有限、誰もがこれは有限だと認める有限である。そのポイントは後出し禁止である。じゃんけんと同じだ。以上。
逆に、後出しという対応は強力なので、結果的に有限の数であっても、純粋な本物の有限とは扱われない（ことが多いある）のだ。二人の子供がより大きな数（自然数）を言うというゲームをしたとすれば、後から言ったほうが大きな数になる。これは自然数が無限個あるということに対応しているので、なかなかに不純なのである。
しかし、最近のプログラミング言語は動的割当が得意なので、うっかりすると後出しで配列サイズを決めたり出来るから困りものである。COBOLとかを使おう。
非決定性はゲームの木の探索
非決定性って言われると、オートマトンを現実のプログラムとして作る時にランダムに状態遷移を選ぶのかって思って混乱するけれど、そうではない。可能な状態遷移をすべて試せばいいのだ。可能なものをすべて試すなんていうのは、プログラミングの基本であり、どこにも悩む要素はない。ただし、バカ正直に全部試す必要はなくて、受理状態が見つかればそこで止める。全部探して、受理状態が見つからなければ、入力は受理されない。
これで私がこだわっている、「文法的に正しくない文に対しては正しくないと出力する」ということも問題なく実現できる。
ただし、入力なしで状態遷移するε動作というやつがあると少し厄介だ。探索がループする可能性がある。オーソドックスなオートマトンの本で非決定性の後にε動作が導入されるのも納得できるだろう。それに対する対応としては、オートマトンの定義を同値なものに変えて探索がループしないようするか、または、探索がループしていることを検出するようなプログラムにする必要があるだろう。
