有限自动机理论(第四版)

第1章 基础知识 形式语言与自动机理论包括3方面的内容：形式语言理论、自动机理论和形式语言与自动机等价性理论。本书主要讨论自动机理论和形式语言与自动机等价性理论。 本书内容属于理论计算机科学的理论范畴，所需的数学基础知识较多。本章对形式语言和有限自动机理论中所需的数学基础知识做扼要的介绍，内容包括集合及其运算、关系、证明和证明的方法以及图与树的概念；同时对形式语言和自动机理论中的重要概念及相关术语做简要介绍。 1.1 集合及其运算 集合理论是计算机理论的重要基础，也是形式语言和自动机理论的基础。 一些没有重复的对象的全体称为集合，而这些被包含的对象称为该集合的元素。集合中元素可以按任意顺序进行排列。一般来说，使用大写英文字母表示一个集合。使用.代表空集，表示该集合未包含任何元素。 若集合A包含元素x(也称元素x属于集合A)，则记为x∈A。 若集合A未包含元素x(也称元素x不属于集合A)，则记为。 若一个集合包含的元素个数是有限的，则称该集合为有穷集合。若一个集合包含的元素个数是无限的，则称该集合为无穷集合。 对于任意的有穷集合A，使用|A|表示该集合包含的元素的个数，显然。 对于具体的集合，可以使用明确的、形式化的方法进行描述。 对于元素个数较少的有穷集合，可以采用列举法，即将集合的所有元素全部列出，放在一对花括号中。例如，集合A={0，1，2，3，4，5，6，7，8，9}，表示集合A由0、1、2、3、4、5、6、7、8、9共10个元素组成。 对于集合元素较多的有穷集合和无穷集合，可以使用集合形成模式{x|P(x)}进行描述(也称为命题法)；其中，x表示集合中的任一元素，P(x)是一个谓词，对x进行限定。{x|P(x)}表示由满足P(x)的一切x构成的集合。可以使用自然语言或数学表示法来描述谓词P(x)。 例如，{n|n是偶数}或{n|nmod2=0}，都表示由所有偶数组成的集合。 定义1.1 子集的定义。 对于两个集合A和B，若集合A的元素都是集合B的元素，则称集合A包含于集合B 中(或称集合B包含集合A)，记为A.B，并且称集合A是集合B的子集。若A.B，且集合B中至少有一个元素不属于集合A，则称集合A真包含于集合B中(或称集合B真包含集合A)，记为A.B，此时，称集合A是集合B的真子集。两个集合相等，当且仅当且B.A。注意：不是且。 定义1.2 集合之间的运算。 集合A与集合B的并(或称为集合A与集合B的和)，记为A∪B，是由集合A的所有元素和集合B的所有元素合并在一起组成的集合： A∪B={x|x∈A或x∈B} 集合A与集合B的交，记为A∩B，是由集合A和集合B的所有公共元素组成的集合： A∩B={x|x∈A且x∈B} 集合A与集合B的差，记为A.B，是由属于集合A但不属于集合B的所有元素组成的集合： 若，则将称为集合B(关于集合A)的补，集合A称为集合B的全集(论域)。 思考：什么情况下，A∪B=A，A∩B=A，A.B=A？ 定义1.3 幂集的定义。 设A为一个集合，那么A的幂集为A的所有子集组成的集合，记为2A，即 例1.1 幂集的例子。 集合A={1，2，3}，则A的幂集为 当集合A为有穷集合时，如果集合A包含的元素个数为n，那么集合2A的元素个数(集合A的所有子集的个数)为2n，这就是称2A为集合A的幂集的原因。当集合A为无穷集合时，仍然使用2A表示集合A的幂集，它也是无穷集合。 注意：任何集合A的幂集2A的元素都是集合。空集.是任何集合的子集，因此也是 任何集合A的幂集2A的子集。 定义1.4 笛卡儿乘积的定义。 集合A和B的笛卡儿乘积使用A×B表示(也简记为AB)，它是集合 {(a，b)|a∈A且b∈B} A×B的元素称为有序偶对(a，b)，总是A的元素在前，B的元素在后。A×B与B×A一般不相等。 例如，设A={a，b，c}，B={0，1}，则 A×B={(a，0)，(a，1)，(b，0)，(b，1)，(c，0)，(c，1)} 而 B×A={(0，a)，(0，b)，(0，c)，(1，a)，(1，b)，(1，c)} 思考：什么情况下，A×B=B×A？ 1.2 关系 1.2.1 二元关系 定义1.5 二元关系的定义。 设A和B为两个集合，则A×B的任何一个子集称为A到B的一个二元关系。若R为 A到B的关系，当(a，b)∈R时，可记为aRb。二元关系简称为关系。 若A=B，则称为A上的二元关系。 例1.2 关系的例子。 设A为正整数集合，则A上的关系“<”是集合 {(a，b)|a，b∈A且a　　即 {(1，2)，(1，3)， (2，3)，(2，4)， (3，4)，(3，5)， } 思考：如果集合A和B都是有穷集合，则A到B的二元关系有多少个？A到B的一个二元关系*多可以有多少个元素？*少可以有多少个元素？ 1.2.2 等价关系 设R是集合A上的关系，那么 若对A中的任何元素a，都有aRa，则称R为自反的。 若对A中的任何元素a和b，从aRb能够推出bRa，则称R为对称的。 若对A中的任何元素a、b和c，从aRb和bRc能够推出aRc，则称R为传递的。 定义1.6 等价关系的定义。 若关系R同时是自反的、对称的和传递的，则称R为等价关系。 等价关系的一个重要性质为：集合A上的一个等价关系R可以将集合A划分为若干互不相交的子集，称为等价类。 对A中的每个元素a，使用[a]表示a的等价类，即 [a]={b|aRb} 等价关系R将集合A划分成等价类的数目称为该等价关系的指数。 例1.3 等价关系的例子。 考虑非负整数集合N上的模3同余关系R： R={(a，b)|a，b∈N且a mod 3=b mod 3} 则集合 {0，3，6， ，3n， } 形成一个等价类，记为[0]。 集合 {1，4，7， ，3n+1， } 形成一个等价类，记为[1]。 集合 {2，5，8， ，3n+2， } 形成一个等价类，记为[2]。由于 N=[0]∪[1]∪[2] 因此R的指数为3。 1.2.3 关系合成 关系是可以合成的。 定义1.7 关系合成的定义。 设是集合A到B的关系，设R2.B×C是集合B到C的关系，则R1和R2的合成是集合A到C的(二元)关系。R1和R2的合成记为R1vR2，则有 R1vR2={(a，c)|(a，b)∈R1且(b，c)∈R2} 例1.4 关系合成的例子。 设 R1和R2是集合{1，2，3，4}上的关系， 定义1.8 关系的n次幂的定义。 设R是S上的二元关系，则关系的n次幂Rn有如下递归定义： 定义1.9 关系的闭包定义。 设R是S上的二元关系，R的正闭包R+定义为 (1) R∈R+； (2)若(a，b)，(b，c)∈R+，则(a，c)∈R+； (3)除(1)和(2)外，R+不再含有其他任何元素，即 R+=R∪R2∪R3∪ 且当S为有穷集合时，有 R+=R∪R2∪R3∪ ∪R|S| 设 R是S上的二元关系，R的克林尼(Kleene)闭包R*定义为 例1.5 关系闭包的例子。 设R1和R2是集合{a，b，c，d，e}上的二元关系，且 R1={(a，b)，(c，d)，(b，d)，(b，b)，(d，e)} R2={(a，a)，(b，c)，(d，c)，(e，d)，(c，a)} 求R1vR2，R1+，R1*。 (1)R1vR2={(a，c)，(c，c)，(b，c)，(d，d)} (2)R1+={(a，b)，(c，d)，(b，d)，(b，b)，(d，e)，(a，d)，(a，e)，(c，e)，(b，e)} (3)R1*={(a，a)，(b，b)，(c，c)，(d，d)，(e，e)}∪R1+ 1.3 证明和证明的方法 形式语言和有限自动机有很强的理论性，许多论断是以定理的形式给出的，而定理的正确性是需要进行证明的。形式语言和有限自动机理论中定理的证明，大多使用反证法和归纳法进行。 1.3.1 反证法 反证法也称为归谬法。利用反证法证明一个命题时，一般步骤如下。 (1)假设该命题不成立。 (2)进行一系列的推理。 (3)如果在推理的过程中，出现了下列情况之一： ①得出的结论与已知条件矛盾； ②得出的结论与公理矛盾； ③得出的结论与已证明过的定理矛盾； ④得出的结论与临时的假定矛盾； ⑤得出的结论自相矛盾； 则可以断言“假设该命题不成立”的假定是不正确的。 (4)肯定原来的命题是正确的。 例1.6 反证法举例。 利用反证法证明 2是无理数。 证明：假设2不是无理数，那么2是有理数，则2可以记为n，而且n和m是互m质的，即n和m的*大公约数为1。 则 所以，n是偶数。令n=2k，则 (2k)2=2m2 4k2=2m2 2k2=m2 所以，m是偶数。 n和m都是偶数，与n和m的*大公约数为1矛盾。所以假设不成立，因此得证2是无理数。 思考：18是完全平方数吗？ 1.3.2 归纳法 归纳法就是从特殊到一般的推理方法。归纳法分为完全归纳法和不完全归纳法两种形式。完全归纳法是根据一切情况的分析而做出的推理。由于必须考虑所有的情况，所以得出的结论是完全可靠的。不完全归纳法是根据一部分情况做出的推理，因此它不能作为严格的证明方法。 在形式语言与有限自动机理论中，大量使用数学归纳法来证明某个命题。数学归纳法可以使用“有限”的步骤来解决“无限”的问题。数学归纳法的步骤如下。 假定对于一切非负整数n，有一个命题M(n)： (1) M(0)为真； (2)设对于任意的k≥0，M(k)为真；若能够推出M(k+1)为真，则对一切n≥0，M(n)为真。 因此，在使用数学归纳法证明某个关于非负整数n的命题P(n)时，只需要证明(1)、(2)两点即可。第(1)步称为归纳基础，第(2)步称为归纳步骤。第(2)步中“设对于任意的k≥0，M(k)为真”称为归纳假设。 在实际应用中，某些命题P(n)并非对n≥0都成立，而是对n≥N(N为大于0的某个自然数)成立，此时，也一样可以使用该归纳法。具体步骤如下。假定对于一切非负整数n，有一个命题M(n)： (1)M(N)为真；