1. 集合演算
A,Bを集合としたとき、以下の演算がよく用いられる。
1.1. 和集合
和集合は、2つ以上の集合を合わせてできる集合のことで、記号は ∪ で表されます。例えば、集合 A={1,2,3} と集合 B={3,4,5} の和集合は A∪B={1,2,3,4,5} となります。
1.2. 積集合
積集合は、2つ以上の集合に共通する要素からなる集合のことで、記号は ∩ で表されます。例えば、集合 A={1,2,3} と集合 B={3,4,5} の積集合は A∩B={3} となります。
1.3. 差集合
差集合は、ある集合から別の集合の要素を取り除いた集合のことで、記号は − で表されます。例えば、集合 A={1,2,3} から集合 B={3,4,5} の要素を取り除いた差集合は A–B={1,2} となります。
1.4. 直積
直積は、2つ以上の集合の組み合わせ(順序対)によってできる集合のことで、記号は × で表されます。例えば、集合 A={1,2} と集合 B={3,4} の直積は A×B={(1,3),(1,4),(2,3),(2,4)} となります。
1.5. 冪集合
冪集合は、ある集合の全ての部分集合からなる集合のことで、記号は 2A で表されます。
例えば、集合 A={1,2} の冪集合は 2A={∅,{1},{2},{1,2}}となります。要素数がn個の集合のべき集合の要素数は2n個となります。今回の場合は、Aの要素数が2個であるので、冪集合の要素数は22=4となっています。言語では∅は空記号列ϵであらわされます。
2. アルファベット ∑
アルファベットは、有限の文字の集合で構成されていて、∑という記号であらわされます。
例えば、
∑={0,1}
∑={a,b}
とのように使用されます。∑={0,1}の例では、0と1から構成される文字列を作ることができます。∑は数列のシグマとは使い方が違います。
3. 語・文字列に関する用語・記号
3.1. 語・文字列
語・文字列とはアルファベットΣ上の記号からなる0文字以上の文字を並べたものです。
例えば、∑={0,1}のときの文字列は0,1,00,000000,1111111111,10101のようなものがあげられます。
3.2. 語の長さ
語の長さとは文字列xに含まれている文字の個数を表しています。語の長さは∣x∣とあらわします。
例えば、x=0101であったとすると、∣x∣=4となります。
3.3. 空記号列ϵ
空記号列ϵ(イプシロン)は語の長さが0であるものです。例えば、0ϵϵϵϵ1111110ϵ111=01111110111となる。
4. 言語に関する用語・記号
4.1. 言語
アルファベット∑上で構成される文字列の集合のことです。∑={a,b}のとき、
L={a,b,bba,aaaa,bbbababa,⋯}
とのように、言語Lを表すことができます。Lは有限集合、無限集合でも構いません。
4.2. 連接
2つの言語 L1 と L2 の連接 L1⋅L2 は、L1 の任意の文字列にL2 の任意の文字列を連結した文字列からなる言語です。つまり、L1⋅L2={w1w2∣w1∈L1,w2∈L2} と定義されます。例えば、L1={a, b} かつ L2={c, d} のとき、L1⋅L2={ac, ad, bc, bd} となります。
4.3. クリーネ閉包
クリーネ閉包はスター閉包とも呼ばれます。クリーネ閉包は以下のように定義されます。クリーネ閉包は、ある言語 L に対して、L から任意回の連接と任意の反復を適用して得られる言語の集合を指します。具体的には、言語 L のクリーネ閉包 L∗ は、以下のように定義されます。
L∗=i≥0⋃Li
このとき、i=0のときは、L0={ϵ}、i>1のときは、Li=Li−1Lであらわされる。
⋃は集合の和集合を意味します。つまり、L∗=i≥0⋃Liは以下のようにあらわすことができます。
L∗=i≥0⋃Li=L0∪L1∪L2∪⋯
また、Li=Li−1LはLiはLi−1とLの連接であらわされるという意味です。
クリーネ閉包の例を次に示します。例えば、L={a, b} とすると、L のクリーネ閉包はL∗={ϵ, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, …} となります。そのときの、L0,L1,L2は以下のように求めることができます。
L0={ϵ}
L1=L0⋅L
={a,b}
L2=L1⋅L
={ab,aa,ba,bb}
4.4. 正閉包
正閉包はクリーネ閉包から空記号列ϵを除いた集合のことです。言語がLのときはL+という記号を用います。
L+=i≥1⋃Li
例えば、L={a, b} とすると、L の正閉包はL+={ a, b, aa, ab, ba, bb, aaa, aab, aba, abb, …} となります。