どうも、木村(@kimu3_slime)です。
次のツイートを見て、”\(3+5=35\)”となる世界を数学的に作れることを思い出しました。今回は、文字列の和・結合、自由モノイドとは何か、簡単に紹介します。
3+5がどうしても35だとしか思えない人の数がどんなに多くても3+5は本当は8だとはいえるにしても、そのことを3+5が35だとしか思えない大多数の人々に決して説明できない(納得させることができない)場合はどうなるかという問題はやはり存在しますよ。
— 永井均 (@hitoshinagai1) June 16, 2021
文字列の和とは
プログラミング言語では、数以外のデータとして、文字列(string)を扱えます。例えばJuliaなら、文字列3と文字列5を結合すると、35という文字列が得られるわけです。
こういった文字列の計算を、数学的に定式化してみましょう。数学というと数しか扱えないイメージがあるかもしれませんが、文字や記号は数学の範囲内です。
文字列とは何かというと、文字をいくつか並べたものです。そこでまず、文字の集合を指定しましょう。
今回は、\(X=\{1,2,3,4,5\}\)という文字の集合を考えます。\(1,2,3,4,5\)というのは単なる文字・記号(symbol)であり、\(a,b,c,d,e\)と書いても同じ議論です。文字列を作るための記号を、アルファベット(alphabet)と呼ぶこともあります。
\(X\)上の文字列(string)、単語(word)とは、文字を順番を考えて並べた有限列と定義します。例えば、\(A=(3,5)\)や\(B=(1,2,3,2,1)\)は文字列です。
\(n\)文字の文字列\((a_1,\dots,a_n)\)は、数学的には順序対と捉えれば良いでしょう。数列が関数であるのと同じように、文字列を有限集合から\(X\)への写像と見ても良いです。
文字列を省略した表記法として、\(35 =(3,5)\)、\(12321=(1,2,3,2,1)\)と書くことにします。より文字列に見えやすくなりました。1文字の文字列を\(3 =(3)\)と書きます。文字そのもののの記号と1文字からなる文字列は厳密に言えば別物なのですが、同じ記号を使って書いていることに注意。
文字列は有限個並んだものですから、必ずそこに文字列の長さ(length)、文字数が定まっています。それを\(|35|=2\)、\(|12321|=5\)と書くことにしましょう。
では、文字列に対して和を考えましょう。文字列の連結(string concatenation)とも呼ぶようです。ここでは和と暫定的に呼んでいますが、積と呼び、積の記号を使っても全く問題ないです。
\(3+5 =35\)となるような”和”を考えたいです。つまり、\((3)+(5) = (3,5)\)とすれば、文字列から新たに文字列が作れます。
一般に、文字列\(A=(a_1,\dots,a_n)\)、\(B=(b_1,\dots,b_m)\)に対し、その和を
\[ \begin{aligned}A+B:=(a_1,\dots,a_n,b_1,\dots,b_m)\end{aligned} \]
と定義します。文字の長さを比べると、\(|A|+|B|=|A+B|=n+m\)が成り立っていますね。
このようにすれば、\(3+5=35\)という式が正当化されました。このルールにおいては、\(5+3 =53\)で、\(3+5 \neq 5+3\)です。文字列の和では、交換法則(可換性)が成り立ちません。
後の都合のため、文字を何も使わない文字列(空文字列)を導入しましょう。\(” “\)と空白記号を使ったら見えないので、\(I\)で表すことにします。\(35 + I =35\)で、一般には\(A+I = I+A =A\)です。空文字列の長さは0 \( |I| =0\)と考えれば良いでしょう。
形式言語、自由群
\(L:=\{X 上の文字列\}\)という集合を、\(X\)上の言語(language)、形式言語(formal language)と言います。
以上で定めた演算\(+\)は、文字列\(A,B \in L\)に対し、和も新たな文字列として\(A+B \in L\)を満たしています。さらに、\(L\)に一定の規則(代数的構造)を与えていることがわかります。
- 結合法則:\(A,B,C \in L\)ならば、\((A+B)+C =A+(B+C)\)
- 単位元の存在:\(A \in L\)に対し、\(A+I =I+A =A\)
結合法則は、どちらを優先して足しても結果が同じであることからわかります。単位元は、そういうものがあるように空文字列\(I\)を定めたのでした。
以上の条件を満たしているとき、\(L\)(と演算\(+\))をモノイド(monoid)と呼びます。
抽象代数学では、モノイドにひとつ条件
- 逆元の存在:\(A \in L\)に対し、\(A+B = B+A =I\)を満たす\(B\)が存在する。
を加えた群(group)をよく考えます。
参考:群論入門~回転群と巡回群を例に、群の定義・同型・位数を解説
今までのセッティングだと、\(L\)はモノイドではあっても群にはなりません。文字列の和は足し合わせであり、文字数が減ることがなく、文字列に何かを加えて空文字にはしようがないのです。
しかし、少し工夫をすると群にできることが知られています。\(X^{-1}:=\{1^{-1},2^{-1},3^{-1},4^{-1}, 5^{-1}\}\)という消す用の(形式的な)文字を用意し、\(L(X \cup X^{-1})\)を舞台にする。そして、\(322^{-1}5 \sim 35\)と、「逆」の文字が隣り合ったらキャンセルできるようにします。つまり、文字の簡約で移り合う文字列を同一視して、同値関係\(\sim\)を考えるわけです。すると、商集合\(L(X \cup X^{-1})/ \sim\)は群になると言えます。例えば、\([35]\)の逆元としては、\([5^{-1} 3^{-1}]\)が選べるわけですね。
詳しくは、例えば堀田「代数入門: 群と加群」4章を参照。
今回紹介したような、文字列からなるモノイド、群は、それぞれ自由モノイド(free monoid)、自由群(free group)と呼ばれるものです。
参考:自由群 – Wikipedia、Free group – Wikipedia
(例えば、1文字\(X=\{1\}\)から生成される自由群は、整数\(\mathbb{Z}\)と考えることができます。どんな整数も、\(1,-1\)を足してできた文字列として捉えられますね。)
以上、\(3+5=35\)となる世界として、文字列の和・結合とは何か、それが自由モノイド・自由群と呼ばれる枠組みを生み出すことを紹介してきました。
\(3+5\)という表現があったから、多くの場合は数の足し算であると解釈して\(8\)と考えるでしょう。ただ、文字列との和として解釈すれば、\(35\)とも言えるわけですね。表現は、解釈が決まらなければ定まった意味を持ちません。
文字列の和や形式言語の考え方は、計算機科学(コンピュータサイエンス)や数理論理学でも用いられるものです。もし興味を持ったら、少し勉強してみてはいかがでしょうか。
木村すらいむ(@kimu3_slime)でした。ではでは。
共立出版 (2000-04-15T00:00:01Z)
![5つ星のうち4.2 5つ星のうち4.2](https://images-fe.ssl-images-amazon.com/images/G/09/x-locale/common/customer-reviews/ratings/stars-4-0.gif)
¥7,412 (中古品)
裳華房 (1987-09-20T00:00:01Z)
![5つ星のうち3.8 5つ星のうち3.8](https://images-fe.ssl-images-amazon.com/images/G/09/x-locale/common/customer-reviews/ratings/stars-4-0.gif)
¥3,410
こちらもおすすめ
コンピュータによる計算(アルゴリズム)とは何か、モデル化の方法、その限界は?