定義:Σ上の語x=a1a2…an,y=b1b2…bmを続けてできる語a1a2…anb1b2…bmxと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=「」

  1. Σは連接に関して単位元εをもつ半群をなす。
  2. 帰納法の原理
    Σの部分集合Xについて、

    • ε∈X
    • x∈X,a∈Σ ⇒ xa∈X

    ならば、X=Σ

  3. 語の分解の一意性
    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」
 群は覚えてるけど、半群ってなんだっけ。群の演算に関して交換法則を必ずしも満たさない、ってことかな。

Post filed under 自習.

One Comment

  1. admin says:

    半群
    http://ja.wikipedia.org/wiki/%E5%8D%8A%E7%BE%A4
    そんな単純なモノではないのね。orz

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です