オートマトンや形式文法でよく出る～記号・用語～

1. 集合演算

A,Bを集合としたとき、以下の演算がよく用いられる。

1.1. 和集合

和集合は、2つ以上の集合を合わせてできる集合のことで、記号は $\cup$ で表されます。例えば、集合 $A = \lbrace 1, 2, 3 \rbrace$ と集合 $B = \lbrace 3, 4, 5\rbrace$ の和集合は $A \cup B = \lbrace 1, 2, 3, 4, 5\rbrace$ となります。

1.2. 積集合

積集合は、2つ以上の集合に共通する要素からなる集合のことで、記号は $\cap$ で表されます。例えば、集合 $A = \lbrace 1, 2, 3\rbrace$ と集合 $B = \lbrace 3, 4, 5\rbrace$ の積集合は $A \cap B = \lbrace 3\rbrace$ となります。

1.3. 差集合

差集合は、ある集合から別の集合の要素を取り除いた集合のことで、記号は $-$ で表されます。例えば、集合 $A = \lbrace 1, 2, 3 \rbrace$ から集合 $B = \lbrace 3, 4, 5 \rbrace$ の要素を取り除いた差集合は $A – B = \lbrace 1, 2\rbrace$ となります。

1.4. 直積

直積は、2つ以上の集合の組み合わせ（順序対）によってできる集合のことで、記号は $\times$ で表されます。例えば、集合 $A = \lbrace 1, 2\rbrace$ と集合 $B = \lbrace 3, 4\rbrace$ の直積は $A \times B = \lbrace (1, 3), (1, 4), (2, 3), (2, 4)\rbrace$ となります。

1.5. 冪集合

冪集合は、ある集合の全ての部分集合からなる集合のことで、記号は $2^A$ で表されます。

例えば、集合 $A = \lbrace 1, 2\rbrace$ の冪集合は $2^A = \lbrace\emptyset, \lbrace 1\rbrace, \lbrace 2\rbrace, \lbrace 1, 2\rbrace\rbrace$となります。要素数が$n$個の集合のべき集合の要素数は$2^n$個となります。今回の場合は、Aの要素数が$2$個であるので、冪集合の要素数は$2^2=4$となっています。言語では$\emptyset$は空記号列$\epsilon$であらわされます。

2. アルファベット　$\displaystyle\sum$

アルファベットは、有限の文字の集合で構成されていて、$\displaystyle\sum$という記号であらわされます。

例えば、

$\displaystyle\sum=\lbrace 0,1\rbrace$

$\displaystyle\sum=\lbrace a,b\rbrace$

とのように使用されます。$\displaystyle\sum=\lbrace 0,1\rbrace$の例では、0と1から構成される文字列を作ることができます。$\displaystyle\sum$は数列のシグマとは使い方が違います。

3. 語・文字列に関する用語・記号

3.1. 語・文字列

語・文字列とはアルファベットΣ上の記号からなる0文字以上の文字を並べたものです。
例えば、$\displaystyle\sum=\lbrace 0,1\rbrace$のときの文字列は$ 0,1,00,000000,1111111111,10101$のようなものがあげられます。

3.2. 語の長さ

語の長さとは文字列xに含まれている文字の個数を表しています。語の長さは$|x|$とあらわします。
例えば、$x=0101$であったとすると、$|x|=4$となります。

3.3. 空記号列$\epsilon$

空記号列$\epsilon$（イプシロン）は語の長さが0であるものです。例えば、$0\epsilon\epsilon\epsilon\epsilon 1111110\epsilon 111=01111110111$となる。

4. 言語に関する用語・記号

4.1. 言語

アルファベット$\displaystyle\sum$上で構成される文字列の集合のことです。$\displaystyle\sum=\lbrace a,b\rbrace$のとき、

$L=\lbrace a,b,bba,aaaa,bbbababa,\cdots\rbrace$

とのように、言語$L$を表すことができます。$L$は有限集合、無限集合でも構いません。

4.2. 連接

2つの言語 $L_1$ と $L_2$ の連接 $L_1\cdot L_2$ は、$L_1$ の任意の文字列に$L_2$ の任意の文字列を連結した文字列からなる言語です。つまり、$L_1\cdot L_2 = \lbrace w_1w_2 \mid w_1 \in L_1, w_2 \in L_2\rbrace$ と定義されます。例えば、$L_1 = \lbrace\text{a, b}\rbrace$ かつ $L_2 = \lbrace\text{c, d}\rbrace$ のとき、$L_1\cdot L_2 = \lbrace\text{ac, ad, bc, bd}\rbrace$ となります。

4.3. クリーネ閉包

クリーネ閉包はスター閉包とも呼ばれます。クリーネ閉包は以下のように定義されます。クリーネ閉包は、ある言語 $L$ に対して、$L$ から任意回の連接と任意の反復を適用して得られる言語の集合を指します。具体的には、言語 $L$ のクリーネ閉包 $L^{*}$ は、以下のように定義されます。

$L^{*}=\displaystyle\bigcup_{i\geq 0} L^i$

このとき、$i=0$のときは、$L^0=\lbrace \epsilon \rbrace$、$i>1$のときは、$L^i=L^{i-1}L$であらわされる。

$\bigcup$は集合の和集合を意味します。つまり、$L^{*}=\displaystyle\bigcup_{i\geq 0} L^i$は以下のようにあらわすことができます。

$L^{*}=\displaystyle\bigcup_{i\geq 0} L^i= L_0 \cup L_1 \cup L_2 \cup \cdots$

また、$L^i=L^{i-1}L$は$L^i$は$L^{i-1}$と$L$の連接であらわされるという意味です。

クリーネ閉包の例を次に示します。例えば、$L=\lbrace\text{a, b}\rbrace$ とすると、$L$ のクリーネ閉包は$L^{*} = \lbrace\epsilon, \text{　a, b, aa, ab, ba, bb, aaa, aab, aba, abb, }\ldots\rbrace$ となります。そのときの、$L^0,L^1,L^2$は以下のように求めることができます。

$L^{0}=\lbrace \epsilon \rbrace$

$L^{1}=L^{0}\cdot L$

$=\lbrace a,b \rbrace$

$L^{2}=L^{1}\cdot L$

$=\lbrace ab,aa,ba,bb \rbrace$

4.4. 正閉包

正閉包はクリーネ閉包から空記号列$\epsilon$を除いた集合のことです。言語が$L$のときは$L^{+}$という記号を用います。

$L^{+}=\displaystyle\bigcup_{i\geq 1} L^i$

例えば、$L=\lbrace\text{a, b}\rbrace$ とすると、$L$ の正閉包は$L^{+} = \lbrace\text{　a, b, aa, ab, ba, bb, aaa, aab, aba, abb, }\ldots\rbrace$ となります。