今まで（金曜日と今日）の話をまとめると、リスト、バッグ、セットのいずれに対しても2項演算・と定数Iが定義できて、さらに、それぞれのパワー（ベキ集合）上に・とIを持ち上げることができる、ってことでした。
そして、パワーの上でも次の計算法則が成立します。
- (A・B)・C = A・(B・C) （どの場合でも）
- I・A = A・I = A （どの場合でも）
- A・B = B・A （バッグとセット）
- A・A = A （セット）
つまり、計算法則もパワー上に持ち上がるのです。
パワー上では、集合の合併演算∪があります。便宜上、∪を+で、空集合をO（大文字オー）で表すことにすると、次も成立します。
- (A + B) + C = A + (B + C)
- O + A = A + O = A
- A + B = B + A
- A + A = A
- A・(B + C) = A・B + A・C
- (A + B)・C = A・C + B・C
ようするに、小学校以来慣れ親しんだ算術の法則はそのまま使えると思っていいわけです。ただし、A・A = A と A + A = A は算数とは異質ですけどね。
ここまでで、リスト、バッグ、セットの集合*1が、算術的に扱えることがわかりましたよね。特に、リスト（列）のケースは、列言語の話そのものです。・が（言語の）連接演算、+が合併演算、Iが空列からなる単位言語、Oが空言語ですね。DTDの正規表現記法なら、・が「,」、+が「|」、Iが予約語「EMPTY」に相当します。
さて、正規表現の*（Kleeneスター）が、
A* = I + A + A・A + A・A・A + …
という無限級数表示を持つことはご存じでしょう。この定義は、リストだけでなく、バッグでもセットでも使えます。
もっとも、セットの場合は A* = A? となります。なぜなら、セットの場合は A・A = A なので、A* = I + A + A + A + … と退化します。ところが A + A = A なので、 無限に並んだA達は1個のAになってしまい A* = I + A です。I + A は empty or A を意味するので A? に他なりません。
ともかくも、演算・と演算+、さらに演算*がそろったので、正規表現の解釈が可能になりました。通常の列（リスト）正規表現以外に、バッグ正規表現とセット正規表現を手に入れたことになります。
正規表現の解釈の場となる、演算・、+、*を備えた計算体系をKleene代数と呼びます。Kleene代数（とその拡張）の実例は、想像以上に多いのです。これはつまり、正規表現をもっと広い範囲で利用可能だということです。
（続く）
*1:「セットの集合」ってのも妙だけど、「集合の集合」よりかえってわかりやすいかも。
