文字列の集合は自由モノイドである
文字の集合を \Sigma として、\Sigma 上の文字の有限列の集まりを \Sigma^{*} とします。
このとき、空列 \varepsilon \in \Sigma^{*} と連接 (\_) \cdot (\_): \Sigma^{*} \times \Sigma^{*} \rightarrow \Sigma^{*} が定まり、\langle \Sigma^{*}, \varepsilon, (\_) \cdot (\_) \rangle はモノイドとなります。つまり、単位元と乗法（結合的な二項演算）が与えられています。
このとき、\Sigma は \Sigma^{*} にとっての生成元であり、\Sigma^{*} は \Sigma にとっての生成先です。
とりわけ、この生成は自由生成と呼ばれます。そして、\Sigma^{*} は \Sigma を生成元とする自由モノイドと言います。
ここでの「自由」とは線形代数等における従属や独立に並ぶ概念です。任意の文字列 w \in \Sigma^{*} は一意に因子分解できます。
w = a_1 \cdot a_2 \cdot a_3 \cdots a_{n}
ただし、a_i \in \Sigma、i = 1, 2, 3, \cdots ,n です。つまり、長さ1の文字列の連接として展開できるということです。ただし、空列 \varepsilon は連接を一つもしないで展開したものとします。
一意に因子分解できるとは何か
上記の定義は直観を助けますが厳密ではありません。厳密であるためには普遍性によって定めます。
任意のモノイド \langle M, e, (\_) \cdot (\_) \rangle を考えます。そして、\Sigma を添字集合（index set）とする M の元の列 (x_a)_{a \in \Sigma} を考えます。つまり、x_a \in M です。
これは x : \Sigma \rightarrow M を定めるということです。あるいは、x \in M^{\Sigma} です。
このとき、次の等式を満たすモノイド準同型 \varphi : \Sigma^{*} \rightarrow M が一意に定まります。
ただし、a \in \Sigma^{*} は a \in \Sigma から成る長さ1の文字列です。
モノイド準同型であるため、モノイドの単位元や乗法について以下が成り立ちます。
\begin{align*}
\varphi(\varepsilon) &= e \\
\varphi(u \cdot v) &= \varphi(u) \cdot \varphi(v)
\end{align*}
このモノイド準同型が定義可能であるのは任意の w \in \Sigma^{*} が一意に因子分解できることに由来しています。
w = a_1 \cdot a_2 \cdot a_3 \cdots a_{n}
と長さ1の文字列の連接に因子分解できれば、準同型であることと長さ1についての等式から、
\begin{align*}
\varphi(w) &= \varphi(a_1 \cdot a_2 \cdot a_3 \cdots a_{n}) \\
&= \varphi(a_1) \cdot \varphi(a_2) \cdot \varphi(a_3) \cdots \varphi(a_{n}) \\
&= x_{a_1} \cdot x_{a_2} \cdot x_{a_3} \cdots x_{a_{n}}
\end{align*}
と計算することができます。この定義が正当であることは \text{well-defined} と呼ばれます。一意に因子分解できなければ、上記の式展開は正当ではありません。自由であることはむしろこのような定義可能性から与えられます。
添字付き指数関数
任意のモノイドの元 x \in M について x を底、自然数を指数とする指数関数を考えることができます。
\begin{align*}
x^0 &= e \\
x^1 &= x \\
x^{m + n} &= x^m \cdot x^{n}
\end{align*}
上記の等式は指数法則と呼ばれます。実はこの指数関数が定義可能であるのは自然数の集合 \mathbb{N} が単元集合を生成元とする自由モノイド \langle \mathbb{N}, 0, (\_) + (\_) \rangle であることに由来しています。
なぜ、上記指数法則のみで累乗を考えることができるのか。それは、任意の自然数 n \in \mathbb{N} が次のように一意に因子分解できるからです。
n = 1 + 1 + 1 + \cdots + 1
添字集合が単元集合であるため、あえて添字を付ける必要はありません。文字列の集合が自由モノイドであることは自然数の指数関数の定義可能性を添字付きに拡張したと考えることができます。
逆に \varphi : \Sigma^{*} \rightarrow M は 添字付き M の元の列 (x_a)_{a \in \Sigma} を底とする指数関数 x^{(\_)} と考えれば \varphi が満たすべき等式は次のように書き換えられます。
そして、
\begin{align*}
x^{\varepsilon} &= e \\
x^{u \cdot v} &= x^{u} \cdot x^{v}
\end{align*}
となります。また、式展開も以下のように書き換えられます。
\begin{align*}
x^w &= x^{a_1 \cdot a_2 \cdot a_3 \cdots a_{n}} \\
&= x^{a_1} \cdot x^{a_2} \cdot x^{a_3} \cdots x^{a_{n}} \\
&= x_{a_1} \cdot x_{a_2} \cdot x_{a_3} \cdots x_{a_{n}}
\end{align*}
オートマトンの状態遷移関数
添字付き指数関数の例にオートマトンがあります。
状態空間を Q、文字集合を \Sigma、状態遷移関数 \delta : \Sigma \times Q \rightarrow Q からなる決定性オートマトンを考えます。
状態遷移関数 \delta はある状態 q \in Q で入力文字 a \in \Sigma を受け付けたときに遷移する状態 \delta (q, a) \in Q を定めています。
状態遷移関数は添字集合を \Sigma とする状態遷移関数列 \{\delta_a\}_{a \in \Sigma} と考えられます。ただし、\delta_a : Q \rightarrow Q です。
状態空間 Q 上の自己写像全体は恒等写像 \text{id}_{Q} を単位元、関数合成 \circ を乗法とするモノイドとなります。そのため、\delta を底として\Sigma上の文字列を指数とする指数関数を考えられます。
つまり、w \in \Sigma^{*} を入力したときの状態遷移を次のように計算します。
\begin{align*}
\delta^w &= \delta^{a_1 \cdot a_2 \cdot a_3 \cdots a_{n}} \\
&= \delta^{a_1} \circ \delta^{a_2} \circ \delta^{a_3} \cdots \delta^{a_{n}} \\
&= \delta_{a_1} \circ \delta_{a_2} \circ \delta_{a_3} \cdots \delta_{a_{n}}
\end{align*}
しばしば、これは\delta^{*} : \Sigma^{*} \times Q \rightarrow Q と定義されます。
ただし、このオートマトンは文字列を右から受け付けます。もし、左から受け付けたい場合は関数適用の順序を反転させる等の工夫が必要です。
モナド
圏論の語彙で言えば、集合 \Sigma から集合 \Sigma^{*} を生成する操作は集合の圏 \bold{Set} 上の自己関手 (\_)^{*} : \bold{Set} \rightarrow \bold{Set} となります。
そして、これは集合の圏 \bold{Set} からモノイドの圏 \bold{Mon} への自由関手 F : \bold{Set} \rightarrow \bold{Mon} とモノイドの圏 \bold{Mon} から集合の圏 \bold{Set} への忘却関手 U : \bold{Mon} \rightarrow \bold{Set} の随伴から与えられるモナドです。
つまり、
となります。
モナドは自己関手、単位元（自然変換）、拡張演算子から成るクライスリトリプル \langle T, \eta, (\_)^{\sharp} \rangle で与えられます。自己関手は (\_)^{*} であり、単位元は文字をその文字から成る長さ1の文字列に写す写像、そして、拡張演算子が指数関数になります。
発展
この記事では書きませんが、自由モノイド はある始代数と等しくなります。自由モノイドの観点では自然数や自然数の再帰定義という観点は現れません。しかし、始代数で考えれば再帰的定義という観点が現れます。
いずれそのことは記事にするつもりです。
また、モノイドは公理を付け加えれば可換モノイド、冪等可換モノイドを考えられます。これらは、ブール代数あるいは関係代数そして集合論と関わります。関係代数はオートマトンにも関わります。
Discussion