形式语言与自动机基础知识

形式语言与自动机这门课需要有离散数学的基础，但本科通信工程里没有学过这门课，总结一些这门课中需要的基础知识

1.集合及其运算

1.1子集和真子集

$A$子集：$A \subseteq B​$或$B \subseteq A​$
$A​$是$B​$的真子集：$A \subset B​$或$B \subset A​$
$x​$是$A​$的一个元素：$x \in A​$
$x​$不是$A​$的一个元素：$x \notin A​$

1.2集合的交并差补

$A$和$B$的并集：$A\cup B={x|x\in A或x\in B}$
$A$和$B$的交集：$A\cap B={x|x\in A且x\in B}$
$A$和$B$的差集：$A - B={x|x\in A且x\notin B}$
若$B\subseteq A$我们也称$A−B$为$B$的（关于$A$）补,记作：$\overline B(A)​$

1.3集合的并的推广

设$I​$是某些标号的集合我们将$\displaystyle \bigcup_{i\in I}A_i={x|存在i\in I,使得x\in A_i}​$

1.4A的幂集

$A$的所有子集的集合，记作$2^A={B|B\subseteq A}​$

1.5笛卡尔乘积

$A\times B={(a,b)|a\in A且b\in B}$

1.6集合之间的关系

由$A$到$B$的关系是$A×B$的任何子集。若$A=B$，则称为$A$上的关系。若$R$为$A$到$B$的关系，当$(a,b)$在$R$内时，可写成$aRb​$

1.7集合关系的性质

设$R$是集合$A$上的关系，则有
（1）若对$A$中的任一元素$a$，都有$aRa$，则称$R$是自反的；
（2）若对$A$中的任何元素$a,b$，从$aRb$能够推到出$bRa$，则称$R$是对称的；
（3）若$a,b,c$是$A$中的元素，从$aRb$和$bRc$能够推出$aRc$，则称$R$是传递的；
若关系$R​$同时是自反的，对称的和传递的，则称之为等价关系。
2018-09-22 15:28:12

参考资料

1.《形式语言与自动机》陈有祺编著