【形式语言】第一章绪论

集合

集合：一定范围内的、确定的、并且彼此可以区分的对象汇集在一起形成的整体叫做集合(set)，简称为集(set)
元素：集合的成员为该集合的元素(element)
基数：集合中元素个数
集合的描述形式有列举法和命题法两种

集合的运算

1. 并($\cup$)
2. 交($\cap$)
3. 差($?$)
4. 对称差($?$)
5. 笛卡尔积($\times$)
   A×B={(a,b)∣a∈A&b∈B}A\times B =\{ (a,b) | a \in A \& b \in B\}A×B={ (a,b)∣a∈A&b∈B}
6. 幂集($2^A$)
   所有集合子集(包含本身和空集)
7. 补集($\overline{A}$)

令A = {1,2,3},B = {2,3,4},U = {1,2,3,4}
则A∪B={1,2,3,4},A∩B={2,3},A?B={1},A?B={1,4},A×B={(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,2),(3,3),(3,4)},2A={?,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}},A?={4}A\cup B=\{1,2,3,4\},A\cap B=\{2,3\},A-B=\{1\},A\oplus B=\{1,4\},A\times B = \{(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,2),(3,3),(3,4)\},2^A=\{\empty , \{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\},\overline A = \{4\}A∪B={ 1,2,3,4},A∩B={ 2,3},A?B={ 1},A?B={ 1,4},A×B={ (1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,2),(3,3),(3,4)},2A={ ?,{ 1},{ 2},{ 3},{ 1,2},{ 1,3},{ 2,3},{ 1,2,3}},A={ 4}

关系

二元关系

二元关系：任意的$R?A\times B$ ，称$R$为$A$到$B$上的二元关系。
表示：$(a,b)\in R$也可表示为$aRb$
两个域：A称为定义域，B称为值域
当$A=B$时称$R$为$A$上的二元关系

几种二元关系性质

1. 自反性 2.反自反 3.对称性 4. 反对称性 5. 传递性
   ps:对称和反对称并不是互斥的

等价关系与等价类

等价关系：具有自反性、对称性、传递性的二元关系称为等价关系。
等价类：S的满足如下要求的划分：$S_1$、$S_2$、$S_3$、…、$S_n$、…称为S关于R的等价划分，$S_i$称为等价类。
(1) $S=S_1\cup S_2\cup S_3\cup ...\cup S_n\cup ...$
(2)如果$i?=j$,则$S_i\cap S_j=?$
(3)对于任意的$i$，$S_i$中的任意两个元素$a$、$b$，$aRb$恒成立。
(4)对于任意的$i$，$j$，$i?=j$，$S_i$中的任意元素$a$和$S_j$中的任意元素$b$，$aRb$恒不成立

关系的合成

设$R_1?A\times B$是$A$到$B$ 的关系、$R_2?B\times C$是$B$到$C$的关系，$R_1$与$R_2$的合成$R_1{R}_2$是$A$到$C$的关系：
R1R2={(a,c)∣?(a,b)∈R1且(b,c)∈R2}R_1R_2= \{(a,c)|\exists(a,b)\in R_1且(b,c)\in R_2\}R1?R2?={ (a,c)∣?(a,b)∈R1?且(b,c)∈R2?}

关系的闭包

设P是关于关系的性质的集合，关系R的P闭包(closure)是包含R并且具有P中所有性质的最小关系。

正闭包(传递闭包)

(1)$R?R^{+}$。
(2)如果$(a,b)$，$(b,c)\in R^{+}$,则$(a，c)\in R^{+}$。
(3)除(1)、(2)外，$R^{+}$不再含有其他任何元素。
具有传递性
对于任意的关系R，有
$$R^{+}=R\cup R^2\cup R^3\cup ...\cup R^n\cup ....$$
当S为有穷集(元素所属于的集合)时，有
$$R^{+}=R\cup R^2\cup R^3\cup ...\cup R^{|S|}$$
提供一种求出$R^{+}$的一套算法（S为有穷集时，这是我自己想的，还没有证明）
step1：
求出$R^2$，令$\Delta R=R^2?R,R=R^2\cup R$
step2：
$R^{\prime }=\Delta RR\cup R\Delta R\cup \Delta R\Delta R$
$\Delta R^{\prime }=R^{\prime }?R$
$R=R\cup R^{\prime }$
若$\Delta R^{\prime }==?$，则结束算法，此时$R^{+}==R$
若$\Delta R^{\prime }?=?$，则令$\Delta R=\Delta R^{\prime }$，转step2
PS：“=”均表示赋值

# python代码实现
def getmutify(set1,set2):s = set()for item1 in set1:for item2 in set2:if item1[1] == item2[0]:s.add(item1[0]+item2[1])return sdef getPositiveClosure(R):R_2 = getmutify(R,R)detR = R_2 - RR = R.union(R_2)while True:Rc = getmutify(detR,R).union(getmutify(R,detR)).union(detR,detR)detRc = Rc - RR = R.union(Rc)if len(detRc) == 0:return RdetR = detRcs = getPositiveClosure({
    "ab","bb","bc"})
print(s)

克林闭包

(1)$R^0?R^{?},R?R^{?}$。
(2)如果$(a,b)$，$(b,c)\in R^{+}$,则$(a，c)\in R_{+}$。
(3)除(1)、(2)外，$R_{+}$不再含有其他任何元素。
具有自反性、传递性

未完待续。。。