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

1. 集合演算

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

1.1. 和集合

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

1.2. 積集合

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

1.3. 差集合

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

1.4. 直積

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

1.5. 冪集合

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

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

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

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

例えば、

={0,1}\displaystyle\sum=\lbrace 0,1\rbrace

={a,b}\displaystyle\sum=\lbrace a,b\rbrace

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

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

3.1. 語・文字列

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

3.2. 語の長さ

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

3.3. 空記号列ϵ\epsilon

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

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

4.1. 言語

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

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

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

4.2. 連接

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

4.3. クリーネ閉包

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

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

このとき、i=0i=0のときは、L0={ϵ}L^0=\lbrace \epsilon \rbracei>1i>1のときは、Li=Li1LL^i=L^{i-1}Lであらわされる。

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

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

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

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

L0={ϵ}L^{0}=\lbrace \epsilon \rbrace

L1=L0LL^{1}=L^{0}\cdot L

={a,b}=\lbrace a,b \rbrace

L2=L1LL^{2}=L^{1}\cdot L

={ab,aa,ba,bb}=\lbrace ab,aa,ba,bb \rbrace

4.4. 正閉包

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

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

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

PR