有限オートマトンを数学的に表現する
＜四次元能版エヴァンゲリオン：二人称の内面化＞

スタックやロストから抜け出す方法
http://www.c-player.com/ad00178/thread/1100111229314
の続きです。

内部観測の数学的表現に挑戦している高橋信二氏の「内部観測：脱構築から発達へ」
http://www.e.okayama-u.ac.jp/jafee/paper/a42.pdf
を参考にして考えています。

有限オートマトンを数学的に表現することが課題となってきました。数学的表現なので数学の素人が勝手に解釈することはできません。そこで高橋氏の表現を忠実に引用（「　」で括ります）しながら解説することにします。

「非決定性有限オートマトンG の状態の集合をQ、始状態をq0 ∈ Q、終状態の集合をF ⊆ Q とする。」

これは双六Gのノード（状態）が沢山あり（Q）、そして、双六のスタートをq0として、上がりをFとするということです。Fがqnではないのは複数あるからです。終わりも上がりも終状態だということですね。
ここまでは簡単です。

「状態間の遷移構造は遷移関数δ : Q × Σ → P(Q) で表現される。ただしここでP(X) はX のベキ集合である。」

これは難しいですね。

ある状態から別の状態に移るということですが、その遷移する構造は遷移関数δ で表現します。簡単に言えば、沢山のノードQ×Σがあって、それぞれ分岐していきますから個々にはqi→ｐjですが、それが集まってQ → Pです。 P(Q) で表現されるとします。

これは集合の基本を学んでおかなければなりません。

集合の基本 （ 元、部分集合、べき集合、直積など ）
http://homepage3.nifty.com/rikei-index01/syugou/syugoukihon.html
以下、引用しました。

定義 （ べき集合 ： Power set ）

集合Aの部分集合全体を集合とみなすこともできる。

集合Aの部分集合全体を Ｐ（Ａ） で表し、『 べき集合 』 という。

例えば、A＝｛ １，２，３ ｝ のべき集合は次のように表される。


P(a)={φ,{1},{2},{3},{1,2}.{1,3}.{2,3},{1,2,3}}

なぜ 『 べき集合 』 と呼ばれるのかというと、べき集合の元の数が、２のべき乗（累乗）になるからである。 例えば、上の例では集合Ａの元は３個で、Ｐ（Ａ）の元は２３＝８個になっている。
―――

しかし、これだけでは足らないようです。

ここの遷移関数δ : Q × Σ → P(Q)は有限オートマトン(FA)を理解しないと、先に進めませんので、

中野氏の有限オートマトン(FA)
http://www.msc.cs.gunma-u.ac.jp/~nakano/Au10/note2.html
を参考にして学んでおきましょう。

また有限オートマトンに戻ってしまいましたが、まだ理解不足のようですので、繰り返します。別の視点で見ると新しい発見があるかも知れません。シムハンタの皆さんで数学に弱い人は生成門と同じように本質だけを見ることに注力しましょう。


有限オートマトン(FA)とは中野氏によれば、言語 = 文字列の集合 = 語の集合 = パターン であるということです。

オートマトンとは言語のグラフ（状態の遷移の図）による記述であるとも言っています。

グラフ上の→の列をパス、各→には文字がついているとします。パス上の→の文字の列が語であるということになりますね。

文字の列＝語（abcd,,,）

------a--------b------c----d
状態１ → 状態２ → 状態３→ ・・・

文字の位置がややずれていますが、文字は→の上についているつもりです。

オートマトンとは双六・携帯であるとも言いましたが、外部から順に入力される記号に対して内部状態を次々に変えていき、その結果として何らかの応答を出力するシステムであるとすると自動販売機、からくり人形など人工的なものから、人間や自然現象まで凡そすべての状態を移行させるもの（システム）はオートマトンと言えるでしょう。

続く