定義:Σ上の語x=a1a2…an,y=b1b2…bmを続けてできる語a1a2…anb1b2…bmをxとyの連接(concatenation)、または積とよび、xyと書く。
そういえば、Excelにおいて文字列を連結する関数は=concatenate(A1,B1)だったかな。
連接は結合法則
x(yz)=(xy)z (x,y,z∈Σ)
を満たす。したがって通常、括弧を省略してxyzのように書く。
定義:xの冪とはxn=xx…x (n個の連接)
x0=ε,x1=x
この辺はかんたんに理解できるだろう。
例:「あ」3=「あああ」、「あ」0=「」
- Σ*は連接に関して単位元εをもつ半群をなす。
- 帰納法の原理
Σ*の部分集合Xについて、- ε∈X
- x∈X,a∈Σ ⇒ xa∈X
ならば、X=Σ*
- 語の分解の一意性
a1a2…anb1b2…bm∈Σ(n,m≧0)のとき、a1a2…an=b1b2…bmならばa1=b1,a2=b2,…,an=bm,n=m
ちなみに上の2.の条件「x∈X,a∈Σ ⇒ xa∈X」は、任意の、ということだと思う。「∀x∈X,∀a∈Σ ⇒ xa∈X」
群は覚えてるけど、半群ってなんだっけ。群の演算に関して交換法則を必ずしも満たさない、ってことかな。
One Comment