3+5=35 ?:文字列の和・結合、自由群とは何か

どうも、木村(@kimu3_slime)です。

次のツイートを見て、”\(3+5=35\)”となる世界を数学的に作れることを思い出しました。今回は、文字列の和・結合、自由モノイドとは何か、簡単に紹介します。

 

文字列の和とは

プログラミング言語では、数以外のデータとして、文字列(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)\)に対し、その和を

\[A+B:=(a_1,\dots,a_n,b_1,\dots,b_m)\]

と定義します。文字の長さを比べると、\(|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\)に一定の規則(代数的構造)を与えていることがわかります。

  1. 結合法則:\(A,B,C \in L\)ならば、\((A+B)+C =A+(B+C)\)
  2. 単位元の存在:\(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)と呼ばれるものです。

参考:自由群 – WikipediaFree group – Wikipedia

(例えば、1文字\(X=\{1\}\)から生成される自由群は、整数\(\mathbb{Z}\)と考えることができます。どんな整数も、\(1,-1\)を足してできた文字列として捉えられますね。)

 

以上、\(3+5=35\)となる世界として、文字列の和・結合とは何か、それが自由モノイド・自由群と呼ばれる枠組みを生み出すことを紹介してきました。

\(3+5\)という表現があったから、多くの場合は数の足し算であると解釈して\(8\)と考えるでしょう。ただ、文字列との和として解釈すれば、\(35\)とも言えるわけですね。表現は、解釈が決まらなければ定まった意味を持ちません。

文字列の和や形式言語の考え方は、計算機科学(コンピュータサイエンス)数理論理学でも用いられるものです。もし興味を持ったら、少し勉強してみてはいかがでしょうか。

木村すらいむ(@kimu3_slime)でした。ではでは。

計算理論の基礎

計算理論の基礎

posted with AmaQuick at 2021.06.18
マイケル シプサ(著), Sipser,Michael(原著), 治, 渡辺(翻訳), 和夫, 太田(翻訳)
共立出版 (2000-04-15T00:00:01Z)
5つ星のうち4.2
¥7,412 (中古品)

 

代数入門: 群と加群 (数学シリーズ)
堀田 良之(著)
裳華房 (1987-09-20T00:00:01Z)
5つ星のうち3.8
¥3,410

 

こちらもおすすめ

抽象ベクトル空間・線形空間の具体例R^N:順序対と直積集合

数列と関数は似ている:等差・等比数列と一次・指数関数

形式言語、論理式、文とは:公理的集合論に向けて

同値関係、2項関係とは? 整数の合同(mod)を例に

群論入門~回転群と巡回群を例に、群の定義・同型・位数を解説

形式言語、論理式、文とは:公理的集合論に向けて

コンピュータによる計算(アルゴリズム)とは何か、モデル化の方法、その限界は?