オートマトンについて学ぶ
＜四次元能版エヴァンゲリオン：内部観測とオートマトン
＞

状態の移り変わりにスポットライトを当てる
http://www.c-player.com/ad00178/thread/1100111185899
の続きです。

オートマトンの説明はこちらが面白いです。

檜山正幸氏「この機会にマスターしようぜ、正規表現、構文図、オートマトン」
http://d.hatena.ne.jp/m-hiyama/20100603/1275546996

この説明を見ていると、グラフがでてくるのですが、グラフは二つのノード（節）と向きの付いた辺（エッジ）から構成されます。向きを示すのに矢印（有向グラフ）を使うところは圏論と似ていますね。

グラフ＞ 始ノード―□→終ノード
□はラベル（指標）道路標識のようなもの

圏 ＞ f：a→b

有向グラフはノードA とノードB の間のエッジに、A からB の向きのものとB からA の向きのものの二種類を認めるようです。

A→B
B→A

この檜山氏は圏論の伝道者だそうで、この中で、「実は、圏論との相性が非常に良いのです。トレース付きモノイド圏、コンパクト閉圏による定式化まで、この描き方をそのまま使い続けることができます。」と言っていますので、圏論をものしたい四次元能としては、オートマトンはその入口と言えるでしょう。学んでおいても損はなさそうです。

有限オートマトンとは特殊な有向グラフであるということなのですが、有限オートマトンにおいては、ノードを状態、エッジを状態遷移と言います。ノードの一つは始状態と呼ばれ、またいくつかのノードが終状態と呼ばれますが、終わりの状態は複数あってもよいことになっています。


有限オートマトン
状態遷移：始状態→＊→＊→＊→＊→終状態（複数可）

ここで、
＊ ノード
→　エッジ
ですが、途中は分岐（選択）、戻り、休止が可能ですから道路網、回路、パート図、インターネットのようになります。

有限オートマトンは有限ですからノードやエッジが有限です。簡単に喩えると新幹線です。新幹線は東京を出て新大阪が終点ですが、その間、状態を遷移させ、つまり、次に駅に行き、終点まで行きます。新幹線オートマトンは単純ですが、状態の遷移があり、その駅の数が有限です。ただ、途中の分岐がない分、単純なだけです。終点も一つしかありませんし、途中で戻ることもありません。

新幹線は東京から新大阪まで一直線にしか行かないのですから、これは決められたルールです。実際の有限オートマトンは分岐ら戻りもあり、もっと複雑で鉄道網や道路網といった感じになるでしょう。

このことを説明するにはスゴロクを使うともっとよいでしょう。

続く