簡略に記します。
内容：
正規表現の構文
いろいろな場面で正規表現はほんとに役に立ちますよね。正規表現の構文や実装には方言がありますが、どんなケースでも、連接、選択、繰り返しは備えています。これらの演算を、「,」、「|」、「*」で表すことにします。これらの演算子記号以外に、定数リテラルの記号があります。定数リテラル記号の集合を形式言語理論ではアルファベットと呼びます。なぜか、アルファベットをΣ（大文字シグマ）で表す習慣があるのですが、ここではアルファベットをAとします。
アルファベットAから作られる正規表現の集合をRegExp(A)としましょう。RegExp(A)を帰納的（inductive）に定義するなら次のようです。
- アルファベットAの要素は正規表現である。（a∈A ⇒ a∈RegExp(A)）
- 空な式εは正規表現である。（ε∈RegExp(A)）
- E, Fが正規表現なら、(E, F)も正規表現である。（E∈RegExp(A), F∈RegExp(A) ⇒ (E, F) ∈RegExp(A)）
- E, Fが正規表現なら、(E | F)も正規表現である。（E∈RegExp(A), F∈RegExp(A) ⇒ (E | F) ∈RegExp(A)）
- Eが正規表現なら、E* も正規表現である。（E∈RegExp(A) ⇒ E* ∈RegExp(A)）
- 以上により定義された式だけが正規表現である*1。
正規表現の標準的な意味
正規表現には標準的な意味が定まっています。アルファベットAから作られた列（リスト、シーケンス、ストリング、呼び名いろいろ）の全体を A* として、さらにA* のベキ集合（冪集合、powerset）を Pow(A*) とします。RegExp(A)の要素、すなわち正規表現には、Pow(A*) の要素が対応します。Pow(A*) の要素とは、列の集合です。
正規表現Eに対応する列の集合を【E】と書くことにします。E∈RegExp(A) ならば、【E】∈Pow(A*) です。Eの標準的な意味【E】を帰納的（inductive）に定義するなら次のようです。
- a∈A ⇒ 【a】 = {[a]} （[a]は長さ1の列）
- 【ε】 = {[]} （単元集合、[]は空列）
- 【(E, F)】 = 【E】・【F】 （連接）
- 【(E | F)】= 【E】∪【F】 （集合の合併）
- 【E*】= 【E】* （クリーネ・スター）
連接とクリーネ・スターは、列の集合だから定義できる演算です。合併は単なる集合演算です。
例：A = {a, b, c} として、((a, b*), (a | c*)) の意味は次のように計算されます。
【((a, b*), (a | c*))】
= 【(a, b*)】・【 (a | c*)】
= (【a】・【 b*】)・(【a】∪【c*】)
= ({[a]}・{[], [b], [b,b], ...})・({[a]}∪{[], [c], [c,c], ...})
= {[a], [a,b], [a,b,b], ...}・{[a], [], [c], [c,c], ...}
= {[a,a], [a], [a,c], [a,c,c], ...,
[a,b,a], [a,b], [a,b,c], [a,b,c,c], ...,
[a,b,b,a], [a,b,b], [a,b,b,c], [a,b,b,c,c], ...
}
正規表現の一般的な意味
正規表現の意味を定義するときに、Pow(A*) に備わっている演算である、連接、合併、クリーネ・スターを使いました。また、連接演算の単位元である {[]} も使いました。ときに、合併演算の単位元である空集合 {} を使うこともあります。これらの演算と定数を備えているなら、正規表現の意味領域を Pow(A*) に限定する必要はありません。
集合K上に、演算「・」（列の連接とは限りません）、演算「+」、演算「*」、それと定数 0, 1 があって適当な公理を満たすとき、(K, ・, +, *, 0, 1)をクリーネ代数と呼びます。正規表現の標準的な意味と同様にして、クリーネ代数Kに対して意味を定義することができます。アルファベットAに対して、A→K という写像が決まれば、あとは自然に拡張して RegExp(A)→K という意味写像を作れます*2。
クリーネ代数の例には、ある種の有向グラフの集合、逐次プログラムの集合、ブール値の正方行列の集合など（に演算と定数を適切に入れたモノ）があります。演算「・」が可換となる例としては、パリク・ベクトル空間*3（マルチセットの集合）があります。これらの対象にも正規表現の議論を適用できるのです。
正規表現とその意味論の拡張
もう一度 Pow(A*) に戻って考えると、Pow(A*) は「部分集合の集合」なので、合併以外に次のような関係や演算があります。
- X, Y∈Pow(A*) のあいだに、X⊆Y という関係がある。
- X, Y∈Pow(A*) に対して、共通部分 X∩Y を定義できる。
- X, Y∈Pow(A*) に対して、差集合 X＼Y を定義できる。
- X∈Pow(A*) に対して、補集合 Xc を定義できる。
このなかで興味深いのは、順序関係と共通部分です。
クリーネ代数でも、演算「+」（集合の演算では「∪」）から自然に順序が定義できます。しかし、アルファベットにもともと順序が入っているときは、ちょっと違った様相となります。そのことは、5年前に書いた「順序言語」（http://www.chimaira.org/docs/OrderedLanguages.htm）で述べました。
集合の共通部分に相当する演算をミートとして導入したミート付きのクリーネ代数の公理化もあります。僕の経験では、ミートが必要とされる場面はとても多いです。にもかかわらず、あまり注目されないようです*4。Catyでは部分的にミート付きクリーネ代数を実装しているのですが、なかなか使い勝手はいいです。少し詳しく紹介したいな、とは思ってます（思ってはいるけれど(以下略…）。
