自由モノイドについて

自由代数について

符号付き文字列というものを導入するというまでの道すじには自由代数の視点がありました。コンピュータ科学上では文字と文字列というものを対象にします。この2つは代数の視点から見れば、基底と自由モノイドという関係に言い換えることができます。代数の視点に立ったときに、モノイドから群への拡張をコンピュータ科学上でも行えるのではないかという着想が得られました。それを、この記事の上で再現するというのがこの記事、そして他の関連する記事の試みです。
　この記事では、文字と文字列の関係を代数の視点から整理するということを行います。その整理が行われたとき、群への拡張は自然に思えるでしょう。

文字と文字列の関係

文字と文字列の関係は、代数の視点から見れば、基底と自由モノイドという関係に重ねられます。これはコンピュータ科学上で行われる文字から文字列を再帰的に定義するというものとは異なる条件によって定式化されます。ここでは、それに関係する文字と文字列の代数的な関係をここでまとめてみましょう。

文字列がモノイドであること

文字の集合をΣとするとき、Σ上の文字の文字列の集合をΣ*と表します。文字列の集合上には連接と呼ばれる結合的な二項演算が定義され、また、連接における単位元である空列というものが存在します。これらの条件は文字列がモノイドであることを示しています。
　これは自然数の指数関数に関する性質の一般化になっています。そのため、自然数の指数関数についての性質を確認することが、理解の助けになるかもしれません。
自然数上の指数関数について

挿入関数η

各Σの文字aについて、長さ1のΣ*上の文字列aを返す関数が存在します。直観的にはあまりに自明な関数ですが、これは両者を代数的に関係づける上で重要な役割を担います。これを挿入関数ηとして定義されます。
\[ η : Σ → Σ^*\]

指数関数

Mを乗法・と単位元eを持つ任意のモノイドとします。また、f を任意のΣからMへの関数f : Σ → M への関数としたとき、次のようなモノイド準同型f^ : Σ* → M がただ一つ存在します。
\[ f^{η(a)} = f(a) \]

　ポイントフリーに書き換えると次のようになります。
\[ f^＾ \circ η = f\]

　f^がただの関数ではなく、モノイド準同型であるとは次の条件を満たすことを意味しています。
\[ f^ε = e \\
f^{x \cdot y} = f^x \cdot f^y\]

　一般的にはこのような呼び方はされませんが、これをfを底とする指数関数と呼びましょう。
　指数関数が存在することは、文字列の集合の始代数性から証明することができますが、これは多少長くなることですので、別の機会に譲ります。

指数関数の直観的な意味

定義や性質だけを与えたので、多少f^が分かりにくいですが、適当な文字列を与えれば、f^がどのような関数かが分かるでしょう。たとえば、文字列"abcd"をf^に与えると次のように展開されます。
\[ f^{abcd} = f(a) \cdot f(b) \cdot f(c) \cdot f(d) \]

（補足）自由モノイドから自由群へ

以上の自由モノイドの定義は群へ拡張するのはとても簡単です。モノイドの部分を群に書き換えるだけで達成されます。しかし、文字列が文字から再帰的に定義することは、群の場合は、多少面倒なことをしなければなりません。しかし、再帰的に定義される文字列が自由モノイドであることを証明することが、どのように定義すれば自由群を作ることができるかについて、示唆を与えるでしょう。