自由モノイド
free monoid
X の要素のListとその結合演算のこと組
([X], ++, []) なモノイドのことクリーネ閉包の一般化
定義
ここで、
\mathrm{List}(B)はBの元の有限列
[b_1,\cdots,b_n]
\diamondは有限列の結合
[b_1,\dots,b_n]\diamond [b_1',\dots,b_{m}'] \coloneqq [b_1,\dots,b_n,b_1',\dots,b_m']
\mathrm{nil}は空列
[]
このとき、組(\mathrm{List}(B), \diamond, \mathrm{nil})を、Bから生成された自由モノイドと呼ぶ
具体例
元が1つの集合\{\circ\}によって生成される自由モノイドは、(\mathbb{N},0,+)と同一視できる
空集合によって生成される、自由モノイドは自明なモノイドである
どのへんが「自由」？
2\times 3=6のような規則がない ref
[2]\diamond[3] =[23]のようにただの文字列の連結になる
ここに意味論は介在しない
構文論のみで完結する
>公理以外の如何なる制約もない ref
ってどういう意味だ
公理以外の制約があるもの、って具体的にどういうもの？
>このように定義だけを利用して作られたモノイドは自由モノイドと呼ばれる。ref
こっちのほうがギリわかりやすいかも。わからんけど
自由モノイドの一つの要素を得る方法が一つに限られるのが特別なのか
13 を得るときには[1]\diamond[3]しかない一方で、普通のモノイドなら、10+3や6+7などいくつかの方法がある
参考