大変更新に間があったお詫びは次回に述べます。実は下書きは大体できていたのでそれをまずUPします。
ネットワークアルゴリズムはひとまず中断し、これから有限オートマトンと正規表現について見ていきます。プログラミング技術的には正規表現がとても大切ですが、アニメーションの派手さ的には有限オートマトンが一押しです。有限オートマトンの考え方はすっきりしたプログラムを作る際に欠かせないものでもあります。と言うわけでまずは有限オートマトンのアニメーションを出します。
ところで正規表現と有限オートマトンは何か関係あるの、とのお言葉、大変的確なご質問です。実はどちらも文字列、記号列を指定する方法で等しい能力を持つことがわかっています。正規表現は記号列が持つべきパターンを記述して、そのパターンに当てはまる記号列を取り出すことができます。有限オートマトンは、一言で言っちゃえば正規表現をコンピュータで実現したものです。コンピュータで文字列、記号列を処理するとき、最初に特定のパターンを持つ列を抜き出すのが普通です。と言うことで多くのプログラミング言語に正規表現は実装されていて、正規表現を使ったスマートなプログラムが作れます。プログラミング言語の処理系はプログラマが作った正規表現を有限オートマトンに変換して機械語プログラムとしています。
まず、正規表現について極簡単に説明します。「a で始まる5文字の名
前（ファイル名や変数名など）」を考えてみます。X をアルファベットのa からz のいずれかとすれば
aXXXX
が「a で始まる5文字の名前」の共通パターンです。次に「a で始まる5文字かc で終わる3文字の名前」を考えます。 「か」という選択を表現するために記号+を導入します。すると、
aXXXX + XXc
というパターンになります。最後に「a で始まる名前」を考えましょう。長さはどれだけでもよいとします。a の後ろにa からz のいずれかを任意の回数付けられます。0 回でも良い。0回を含む任意回の繰り返しを示す記号を*とします すると「a で始
まる名前」に対応するパターンは
aX*
となります。この式は最初がa で, あとX の中のどれかの文字が0回以上繰り返されることを意味しています。ところで X はa からz のいずれか一つの選択ですから
X=(a+b+ ・・・ +z)
とすべきです。上に出た3つのパターンのX のところにこれを「代入」してたとえば、
a(a+b+ ・・・ +z) *
などが「正式」のパターンの表現法になります。次に数の表現を見てみます。0と1で済ませられる2進数にします。符号なし2進数は0と1の列とはいえ、値0以外は1で始まります。だから
1(0+1)*+0
となります。最後の"+0"はゼロは数字1で始まらないので「1で始まるかまたは0一つだけ」を示します。
プログラムで使う正規表現を知る人は「選択が縦棒"|"でない」とおっしゃるでしょう。プラス記号+は1回以上の繰り返しにも使います。例えば1の後に0が一回以上繰り返すのは 10+ となります。ところがソースプログラムでは右肩に記号を載せることができません。そこでプログラムでは 10+ とかきます。すると選択と全く区別がつかないので、選択には縦棒|が当てられました。プログラミング言語では、パターンに一致した記号列を代入できる変数や行のはじめや終わりなどを指定する記号などパターン記述を便利にする仕掛けがたくさんあります。詳しくは下にリンクを貼った書籍をどうぞ。また、正規表現とオートマトンについて理論を解説した書籍へもリンクを貼ってあります。
