形式语言与自动化理论第一章绪论20160919

1、2022-3-121计算机软件理论基础计算机软件理论基础课程目的和基本要求课程目的和基本要求2022-3-122课程性质课程性质技术基础技术基础 基础知识要求基础知识要求 数学分析数学分析（或者高等数学），（或者高等数学），离散数学离散数学 主要特点主要特点 抽象和形式化抽象和形式化 理论证明和构造性理论证明和构造性 基本模型的建立与性质基本模型的建立与性质 课程目的和基本要求课程目的和基本要求2022-3-123本专业人员本专业人员4 4种基本的专业能力种基本的专业能力计算思维能力计算思维能力算法的设计与分析能力算法的设计与分析能力程序设计和实现能力程序设计和实现能力计算机软硬件系统的认知、

2、分析、设计与应用能力计算机软硬件系统的认知、分析、设计与应用能力计算思维能力计算思维能力逻辑思维能力和抽象思维能力逻辑思维能力和抽象思维能力构造模型对问题进行形式化描述构造模型对问题进行形式化描述理解和处理形式模型理解和处理形式模型课程目的和基本要求课程目的和基本要求 2022-3-124知识知识掌握掌握正则语言正则语言、上下上下文无关语言的文法文无关语言的文法、识别模型及识别模型及其基本性质其基本性质、图灵机的基本知识图灵机的基本知识。能力能力培养学生的形式化描述和抽象思维能力。培养学生的形式化描述和抽象思维能力。使学生了解和初步掌握使学生了解和初步掌握“问题、形式化描述、自动化问题、形式化

3、描述、自动化（计算机化）（计算机化）”这一最典型的计算机问题求解思路。这一最典型的计算机问题求解思路。 主要内容主要内容 2022-3-125语言的语言的文法文法描述。描述。RLRLRGRG、 FAFA、RERE、RLRL的性质的性质 。CFLCFLCFG(CNFCFG(CNF、GNF)GNF)、PDAPDA、CFLCFL的性质。的性质。 TMTM基本基本TMTM、构造技术、构造技术、TMTM的修改。的修改。CSLCSLCSGCSG、LBALBA。教材及主要参考书目教材及主要参考书目2022-3-126蒋宗礼，姜守旭蒋宗礼，姜守旭. 形式语言与自动机理论形式语言与自动机理论. 北京：北京：清华

4、大学出版社，清华大学出版社，2013年年 (第第3版）版）John E Hopcroft, Rajeev Motwani, Jeffrey D Ullman. Introduction to Automata Theory, Languages, and Computation (2nd Edition). Addison-Wesley Publishing Company, 2001 John E Hopcroft, Jeffrey D Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-W

5、esley Publishing Company, 1979成绩评定2022-3-1271. 平时考勤、作业-40%2. 期末考试-60%第第1章章 绪论绪论2022-3-1281.1 集合的基础知识集合的基础知识 1.1.1 集合及其表示集合及其表示集合：集合：一定范围内的一定范围内的、确定的确定的、并且、并且彼此可以区分的对彼此可以区分的对象象汇集在一起形成的整体叫做汇集在一起形成的整体叫做集合集合(set)， ，简简称称为为集集(set)。 。 元素：集合的成元素：集合的成员为该员为该集合的集合的元素元素(element)。 。 集合描述形式。集合描述形式。 基数。基数。 集合的分集合的

6、分类类。 。 1.1.2 1.1.2 集合之间的关系集合之间的关系 2022-3-129子集子集 如果如果集合集合A中的每个元素都是集合中的每个元素都是集合B的元素的元素，则称，则称集合集合A是集合是集合B的的子集子集(subset)，集合，集合B是集合是集合A的的包集包集(container)。记作。记作A B。也可记作。也可记作B A。A B读作集合读作集合A包含在集合包含在集合B中；中；B A读作集合读作集合B包含集合包含集合A。如果如果A B，且，且 xB，但，但x A，则称，则称A是是B的的真子真子集集(proper subset)，记作，记作A B 1.1.2 1.1.2 集合之间

7、的关系集合之间的关系2022-3-1210集合相等集合相等 如果集合如果集合A，B含有的元素完全相同，则称集合含有的元素完全相同，则称集合A与集合与集合B相等相等(equivalence)，记作，记作A=B。对任意集合对任意集合A、B、C： A=B iff A B且且B A。 如果如果A B，则，则|A|B|。 如果如果A B，则，则|A|B|。 如果如果A是是有穷集有穷集，且，且A B，则，则|B|A|。1.1.2 1.1.2 集合之间的关系集合之间的关系2022-3-1211 如果如果A B，则对，则对 xA，有，有xB。如果如果A B，则对，则对 xA，有，有xB并且并且 xB，但，但x

8、 A。 如果如果A B且且B C，则，则A C。 如果如果A B且且B C，或者，或者A B且且B C，或者，或者A B且且B C，则，则A C。 如果如果A=B，则，则|A|=|B|。1.1.3 1.1.3 集合的运算集合的运算 2022-3-1212并并(union) A与与B的的并并(union)是一个集合，该集合中的元素要么是一个集合，该集合中的元素要么是是A的元素，要么是的元素，要么是B的元素，记作的元素，记作AB。 AB=a|aA或者或者aB A1A2An=a| i，1in，使得，使得aAi A1A2An =a| i，iN,使得使得aAi1iiA,|AaSAaASA交交(inter

9、section) 2022-3-1213集合集合A和和B中中都有的都有的所有元素放在一起构成的集合所有元素放在一起构成的集合为为A与与B的的交交 ，记作，记作AB。 AB=a|aA且且aB “”为交运算符，为交运算符，AB读作读作A交交B。 如果如果AB=，则称，则称A与与B不相交。不相交。 AB= BA。 (AB)C=A(BC)。 AA=A。交交(INTERSECTION)2022-3-1214 AB=A iff A B。 A=。 |AB|min|A|，|B|。 A(BC)=(AB)(AC)。 A(BC)=(AB)(AC)。 A(AB)=A。 A(AB)=A。差差(difference)(d

10、ifference) 2022-3-1215属于属于A，但不属于，但不属于B的所有元素的所有元素组成的集合叫做组成的集合叫做A与与B的的差，记作差，记作A-B。 A-B=a|aA且且a B “-”为减为减(差差)运算符，运算符，A-B读作读作A减减B。 A-A=。 A-=A。 A-B B-A。 A-B=A iff AB=。 A(B-C)=(AB)-(AC)。 |A-B|A|。对称差对称差(symmetric difference) 2022-3-1216属于属于A但不属于但不属于B，属于，属于B但不属于但不属于A的的所有元素组成的集所有元素组成的集合叫合叫A与与B的的对称差，记作对称差，记作A

11、BAB。 AB=a|aAAB=a|aA且且a a B B或者或者a a A A且且aB aB “”为对称差运算符。为对称差运算符。ABAB读作读作A A对称减对称减B B。 AB=(AB)-(AB)=(A-B)(B-A)AB=(AB)-(AB)=(A-B)(B-A)。 笛卡儿积笛卡儿积(Cartesian product) 2022-3-1217A与与B的的笛卡儿积笛卡儿积(Cartesian product)是一个集合，是一个集合，该该集合是由所有集合是由所有这样这样的的有序有序对对(a，b)组组成的：其中成的：其中aA，bB ，记记作作AB。 AB=(a，b)|aA& bB 。 “

12、”为笛卡儿乘运算符。为笛卡儿乘运算符。AB读作读作A叉乘叉乘B。 ABBA。 (AB)CA(BC)。 AAA。 A=。笛卡儿积笛卡儿积(CARTESIAN PRODUCT)2022-3-1218 A(BC)=(AB)(AC)。 (BC)A=(BA)(CA)。 A(BC)=(AB)(AC)。 (BC)A=(BA)(CA)。 A(B-C)=(AB)-(AC)。 (B-C)A=(BA)-(CA)。 当当A、B为有穷集时，为有穷集时，|AB|=|A|*|B|。 幂集幂集(power set) 2022-3-1219A幂集幂集(power set)(power set)是一个集合，该集合是是一个集合，该

13、集合是由由A的所的所有子集组成的有子集组成的，记作，记作2A。 2A=B|B A。 2A读作读作A的幂集的幂集。幂集幂集(POWER SET)2022-3-1220 2A。 2A。 2A。 2=。 A2A。 如果如果A是是有穷集有穷集，则，则|2A|=2|A|。 2AB=2A2B。 如果如果A B，则，则2A 2B。 补集补集(complementary set) 2022-3-1221A是论域U上的一个集合，A补集补集是由U中的、不在A中的所有元素组成的集合，记作AUAUU补集补集(COMPLEMENTARY SET)2022-3-1222AABAUBAAB&BABABABAAB U

14、AA如果如果A B，则，则。1.2 1.2 关系关系 2022-3-1223二元关系二元关系 递归定义与归纳证明递归定义与归纳证明 关系的闭包关系的闭包 1.2.1 二元关系二元关系(binary relation) 2022-3-1224二元关系二元关系 任意的RAB，R是A到B的二元关系二元关系。 。 (a，b) R，也可表示为：aRb。 A称为定定义义域域(domain)，B称为值值域域(range)。 当A=B时，则称R是A上的二元关系。二元关系的性质二元关系的性质自反(reflexive)性、反自反(irreflexive)性、对称(symmetric)性、反对称(asymmetri

15、c)性、传递(transitive)性。1.2.1 二元关系二元关系(BINARY RELATION)2022-3-1225三歧性三歧性 自反性、对称性、传递性。自反性、对称性、传递性。等价关系等价关系(equivalence relation) 具有三歧性的二元关系称为等价关系。等价关系。 1.2.2 等价类等价类 (equivalence class) 2022-3-1226等价类等价类 (equivalence class) S的满足如下要求的划分：的满足如下要求的划分：S1、S2、S3、Sn称为称为S关于关于R的等价划分，的等价划分，Si称为等价类。称为等价类。 S= S1S2S3Sn

16、； 如果如果ij，则，则SiSj=； 对任意的对任意的i，Si中的任意两个元素中的任意两个元素a、b，aRb恒成立；恒成立； 对任意的对任意的i，j，ij，Si中的任意元素中的任意元素a和和Sj中的任意元素中的任意元素b，aRb恒不成立恒不成立 1.2.2 指数指数(index)2022-3-1227指数指数(index) 把把R将将S分成的等价类的个数称为是分成的等价类的个数称为是R在在S上的上的指数指数。如果如果R将将S分成有穷多个等价类，则称分成有穷多个等价类，则称R具有有穷指数；具有有穷指数；如果如果R将将S分成无穷多个等价类，则称分成无穷多个等价类，则称R具有无穷指数。具有无穷指数。

17、给定集合给定集合S上的一个等价关系上的一个等价关系R，R就确定了就确定了S的一个的一个等价分类，当给定另一个不同的等价关系时，它会确等价分类，当给定另一个不同的等价关系时，它会确定定S的一个新的等价分类。的一个新的等价分类。 1.2.3 关系的合成关系的合成(composition)2022-3-1228关系的合成关系的合成 (composition) 设设R1 AB是是A到到B的关系、的关系、R2 BC是是B到到C的关系，的关系，R1与与R2的的合成合成R1R2是是A到到C的关系：的关系：R1R2=(a，c)| (a，b) R1且且(b，c) R2 。 1.2.3 关系的合成关系的合成(co

18、mposition)2022-3-1229 R1R2R2R1。 (R1R2)R3=R1(R2R3)。 (结合率结合率) (R1R2)R3=R1R3R2R3。(右分配率右分配率) R3(R1R2)=R3R1R3R2。(左分配率左分配率) (R1R2)R3 R1R3R2R3。 R3(R1R2) R3R1R3R2。1.2.4 递归定义与归纳证明递归定义与归纳证明2022-3-1230递归定义(recursive definition)又称为归纳定义(inductive definition)，可以用来定义一个集合。集合的递归定义由三部分组成：基础(basis)：用来定义该集合的最基本的元素。归纳(i

19、nduction)：指出用集合中的元素来构造集合的新元素的规则。极小性限定：指出一个对象是所定义集合中的元素的充要条件是它可以通过有限次的使用基础和归纳条款中所给的规定构造出来。 1.2.4 递归定义与归纳证明递归定义与归纳证明 2022-3-1231归纳证明归纳证明 与递归定义相对应。与递归定义相对应。 归纳证明方法包括三大步：归纳证明方法包括三大步： 基础基础(basis)：证明最基本元素具有相应性质。：证明最基本元素具有相应性质。 归纳归纳(induction)：证明如果某些元素具有相：证明如果某些元素具有相应性质，则根据这些元素用所规定的方法应性质，则根据这些元素用所规定的方法得到的新

20、元素也具有相应的性质。得到的新元素也具有相应的性质。根据归纳法原理根据归纳法原理，所有的元素具有相应的，所有的元素具有相应的性质。性质。 1.2.4 递归定义与归纳证明递归定义与归纳证明 2022-3-1232定义定义 1-17 设设R是是S上的上的二元二元关系，我们递归地定义关系，我们递归地定义Rn的幂：的幂： R0=(a，a)|aS。 Ri=Ri-1R (i=1,2,3,4,5,)。1.2.4 递归定义与归纳证明递归定义与归纳证明 2022-3-1233例例1-17 1-17 著名的斐波那契著名的斐波那契(Fibonacci)数的定义数的定义 基础：基础：0是第一个斐波那契数，是第一个斐波

21、那契数，1第二个斐波那契数；第二个斐波那契数； 归纳：如果归纳：如果n是第是第i个斐波那契数，个斐波那契数，m是第是第i+1个斐波那个斐波那契数，则契数，则n+m是第是第i+2个斐波那契数，这里个斐波那契数，这里i为大于等于为大于等于1的正整数。的正整数。 只有满足只有满足(1)和和(2)的数才是斐波那契数的数才是斐波那契数 0，1，1，2，3，5，8，13，21，34，55，1.2.4 递归定义与归纳证明递归定义与归纳证明2022-3-1234例例1-18 算术表达式算术表达式 基础：常数是算术表达式，变量是算术表达式；基础：常数是算术表达式，变量是算术表达式； 归纳：如果归纳：如果E1、E

22、2是表达式，则是表达式，则 +E1、-E1、E1+E2、 E1-E2 、E1*E2 、E1/E2、E1E2、Fun(E1)是是算术表达式。其中算术表达式。其中Fun为函数名。为函数名。 只有满足只有满足(1)和和(2)的才是算术表达式。的才是算术表达式。 1.2.4 递归定义与归纳证明递归定义与归纳证明 2022-3-1235例例1-19 对有穷集合对有穷集合A，证明，证明|2A|=2|A|。证明：证明：设设A为一个有穷集合为一个有穷集合, 施归纳于施归纳于|A|： 基础：当基础：当|A|=0时时,|2A|=|=1。 归纳：假设归纳：假设|A|=n时结论成立，这里时结论成立，这里n 0，往证，

23、往证当当|A|=n+1时结论成立时结论成立。不妨假设不妨假设A=B a，a B 2A=2BCa|C2B 2BCa|C2B= 1.2.4 递归定义与归纳证明递归定义与归纳证明 2022-3-1236 |2A|=|2BCa|C2B|=|2B|+|Ca|C2B|=|2B|+|2B|=2*|2B|=2*2|B|=2|B|+1=2|A| 由归纳法原理，结论对任意有穷集合成立。由归纳法原理，结论对任意有穷集合成立。1.2.4 递归定义与归纳证明递归定义与归纳证明2022-3-1237例例1-20 1-20 表达式的前缀形式是指将运算符写在前面，后表达式的前缀形式是指将运算符写在前面，后跟相应的运算对象。如

24、：跟相应的运算对象。如：+E1的前缀形式为的前缀形式为+E1，E1+E2的的前缀形式为前缀形式为+E1E2 ，E1*E2的前缀形式为的前缀形式为*E1E2， E1E2的前的前缀形式为缀形式为 E1 E2，Fun(E1) 的前缀形式为的前缀形式为Fun E1 。证明例证明例1-18所定义的表达式可以用这里定义的前缀形式所定义的表达式可以用这里定义的前缀形式表示。表示。 1.2.4 递归定义与归纳证明递归定义与归纳证明 2022-3-1238递归定义给出的概念有利于归纳证明。在计算机科递归定义给出的概念有利于归纳证明。在计算机科学与技术学科中，有许多问题可以用递归定义描述学与技术学科中，有许多问题

25、可以用递归定义描述或者用归纳方法进行证明，而且在许多时候，这样或者用归纳方法进行证明，而且在许多时候，这样做会带来许多方便。做会带来许多方便。 主要是掌握主要是掌握递归定义与归纳证明递归定义与归纳证明的叙述格式。的叙述格式。 1.2.5 关系的闭包关系的闭包 2022-3-1239闭包闭包(closure)(closure) 设设P是关于关系的性质的集合，关系是关于关系的性质的集合，关系R的的P闭闭包包(closure)(closure)是包含是包含R并且具有并且具有P中所有性质的最小关系中所有性质的最小关系。正闭包正闭包(positive closure)(positive closure)

26、 (1)R R+。(2)如果如果(a，b)，(b，c)R+ 则则(a，c)R+。(3)除除(1)、(2)外，外，R+不再含有其他任何元素不再含有其他任何元素。 1.2.5 关系的闭包关系的闭包2022-3-1240传递闭包传递闭包(transitive closure) 具有传递性的闭包。具有传递性的闭包。R+具有传递性。具有传递性。可以证明，对任意二元关系可以证明，对任意二元关系R， R+= RR2R3R4而且当而且当S为有穷集时：为有穷集时： R+= RR2R3R|S|1.2.5 关系的闭包关系的闭包2022-3-1241克林闭包克林闭包(Kleene closure) R(Kleene

27、closure) R* * (1) R R0 0 R R* *,R,R R R* *。 (2) 如果如果(a(a，b)b)，(b(b，c)Rc)R* * 则则(a(a，c)Rc)R* *。 (3) 除除(1)(1)、(2)(2)外，外，R R* *不再含有其他任何元素。不再含有其他任何元素。 自反传递闭包自反传递闭包(reflexive and transitive (reflexive and transitive closure) closure) R*具有自反性、传递性具有自反性、传递性。1.2.5 关系的闭包关系的闭包2022-3-1242可以证明，对任意二元关系可以证明，对任意二元关

28、系R， R*= R0R+ R* =R0RR2R3R4而且当而且当S为有穷集时：为有穷集时： R*= R0RR2R3R|S| 1.2.5 关系的闭包关系的闭包2022-3-1243R1、R2是是S上的两个二元关系上的两个二元关系 (1) +=。 (2) (R1+)+= R1+ 。 (3) (R1*)*= R1*。 (4) R1+R2+ (R1R2)+。 (5) R1*R2* (R1R2)*。 1.3 图图2022-3-1244直观地讲，图是由直观地讲，图是由一些点一些点和和一些连接两点的边一些连接两点的边组成。组成。含无方向的边含无方向的边的图为无向图，的图为无向图，含带有方向的边含带有方向的边

29、的图的图为有向图。为有向图。 1.3.1 无向图无向图 2022-3-1245无向图无向图(undirected graph) 设设V是一个非空的有穷集合，是一个非空的有穷集合，E VV，G=(V，E)称称为为无向无向图图(undirected graph)。其中。其中V中的元素称为中的元素称为顶顶点点(vertex或或node)，V称为称为顶点集顶点集，E中的元素称为中的元素称为无无向向边边(undirected edge)，E为为无向边集无向边集。图表示图表示V中称为顶点中称为顶点v的元素用标记为的元素用标记为v的小圈表示，的小圈表示，E中的中的元素元素(v1，v2)用标记为用标记为v1，

30、v2的顶点之间的连线表示。的顶点之间的连线表示。 1.3.1 无向图无向图2022-3-1246路路(path)如果对于如果对于0ik-1，k1，均有，均有(vi，vi+1)E，则称，则称v0，v1，vk是是G=(V，E)的一条长为的一条长为k的的路。路。回路或圈回路或圈(cycle)当路当路v0，v1，vk中中v0=vk时，时，v0，v1，vk叫做叫做一个一个回路或圈回路或圈(cycle)。1.3.1 无向图无向图2022-3-1247顶点的度数顶点的度数 对于对于vV，|w|(v，w)E|称为无向图称为无向图G=(V，E)的顶点的顶点v的度数，记作的度数，记作deg(v)。对于任何一个图，

31、对于任何一个图，图中所有顶点的度数之和为图中边的图中所有顶点的度数之和为图中边的2倍倍。 VvEv|*2)deg(2022-3-1248deg(v1)=3deg(v2)=3deg(v3)=4deg(v4)=3deg(v5)=3deg(v1)+deg(v2)+deg(v3)+deg(v4)+deg(v5)=16 1.3.1 无向图无向图2022-3-1249连通图连通图 如果对于如果对于 v，wV，vw，v与与w之间之间至少有一条路至少有一条路存在存在，则称，则称G=(V，E)是是连连通通图图。 图图G是连通的充要条件是是连通的充要条件是G中中存在一条包含图的所有存在一条包含图的所有顶点的路顶点

32、的路。 1.3.2 有向图有向图 2022-3-1250有向图有向图(directed graph) G=(V， ，E)。V：顶顶点点(vertex(vertex或或node)node)集。集。(v1，v2)E：顶点顶点v1到顶点到顶点v2的的有向有向边边(directed (directed edge)edge)，或，或弧弧(arc)(arc)，v1称为称为前前导导(predecessor)(predecessor)，v2称为称为后后继继(successor)(successor)。 。有向路有向路(directed path)(directed path) 如果对于如果对于0ik-1，k1

33、，均有，均有(vi，vi+1)E，则称，则称v0，v1，vk是是G的一条长为的一条长为k的的有向路。有向路。 1.3.2 有向图有向图2022-3-1251有向回路或有向圈有向回路或有向圈(directed cycle) (directed cycle) 对于对于0ik-1，k1，均有，均有(vi，vi+1)E， 且且v0=vk，则称则称v0，v1，vk是是G的一条长为的一条长为k的的有向路有向路为为一个一个有向回路。有向回路。有向回路又叫有向圈。有向回路又叫有向圈。 有向图的图表示有向图的图表示图图G G的图表示是满足下列条件的的图表示是满足下列条件的“图图”：其中：其中V V中称为中称为顶

34、点顶点v v的元素用标记为的元素用标记为v v的小圈表示，的小圈表示，E E中的元素中的元素(v(v1 1，v v2 2) )用从标记为用从标记为v v1 1的顶点到标记为的顶点到标记为v v2 2的顶点的弧表示的顶点的弧表示。 1.3.2 有向图有向图2022-3-1252顶点的度数顶点的度数 入度入度( (数数) )：ideg(v)=|w|(w，v)E|。 出度出度( (数数) )：odeg(v)= |w|(v，w)E|。 对于任何一个有向图，图中所有顶点的入度之和与图对于任何一个有向图，图中所有顶点的入度之和与图中所有顶点的出度之和正好是图中边的个数中所有顶点的出度之和正好是图中边的个数

35、 VvVvEvovi|)deg()deg(2022-3-1253两个不同的有向图两个不同的有向图1.3.3 树树 2022-3-1254满足如下条件的有向图满足如下条件的有向图G=(V，E)称为一棵称为一棵(有序、有序、有向有向)树树(tree)： 根根(root) v：没有前导没有前导，且，且v到树中其他顶点均有一条到树中其他顶点均有一条有向路。有向路。每个非根顶点有且仅有一个前导每个非根顶点有且仅有一个前导。 每个顶点的后继按其拓扑关系从左到右排序每个顶点的后继按其拓扑关系从左到右排序。 1.3.3 树树 2022-3-1255树的基本概念树的基本概念 (1) 顶点也可以成为结点顶点也可以

36、成为结点。(2) 结点的前导为该结点的结点的前导为该结点的父亲父亲(父结点父结点father)。(3) 结点的后继为它的结点的后继为它的儿子儿子(son)。(4) 如果树中有一条从结点如果树中有一条从结点v1到结点到结点v2的路，则称的路，则称v1是是v2的的祖先祖先(ancestor), v2是是v1的的后代后代(descendant)。(5) 无儿子的顶点叫做无儿子的顶点叫做叶子叶子(leaf)。(6) 非叶结点叫做非叶结点叫做中间结点中间结点(interior)。1.3.3 树树 2022-3-1256树的层树的层 根处在树的第根处在树的第1层层(level)。 如果结点如果结点v处在第

37、处在第i层层(i1)，则，则v的儿子处在第的儿子处在第i+1层层。树的最大层号叫做该树的高度树的最大层号叫做该树的高度(height)。 1.3.3 树树 2022-3-1257二元树二元树 如果对于如果对于 vV，v最多只有最多只有2个儿子个儿子，则称，则称G=(V，E)为为二元二元树树(binary tree)。 对一棵二元树，它的第对一棵二元树，它的第n层最多有层最多有2n-1个结点。一棵个结点。一棵n层层二元树最多有个二元树最多有个2n-1叶子。叶子。 1.4 语言语言 2022-3-12581.4.1 1.4.1 什么是语言什么是语言 例如：例如：“学大一生是个我学大一生是个我”；“

38、我是一个大学生我是一个大学生”。 语言是一定的群体用来进行交流的工具语言是一定的群体用来进行交流的工具。 必须有着一系列的生成规则、理解必须有着一系列的生成规则、理解(语义语义)规则规则。1.4.1 什么是语言什么是语言 2022-3-12591.4.1 什么是语言什么是语言 2022-3-1260斯大林：从强调语言的作用出发，把语言定义为斯大林：从强调语言的作用出发，把语言定义为“为广大的人群所理解的字和组合这些字的方法为广大的人群所理解的字和组合这些字的方法”。 语言学家韦波斯特语言学家韦波斯特(Webster) ：为相当大的团体的：为相当大的团体的人所懂得并使用的字和组合这些字的方法的统

39、一体。人所懂得并使用的字和组合这些字的方法的统一体。 要想对语言的性质进行研究，用这些定义来建立语要想对语言的性质进行研究，用这些定义来建立语言的数学模型是不够精确的。言的数学模型是不够精确的。必须有更形式化的定必须有更形式化的定义义。 1.4.2 形式语言与自动机理论的产生与形式语言与自动机理论的产生与作用作用 2022-3-1261语言学家乔姆斯基，毕业于宾西法尼亚大学，最初语言学家乔姆斯基，毕业于宾西法尼亚大学，最初从产生语言的角度研究语言。从产生语言的角度研究语言。1956年，他将语言年，他将语言L定义为一个字母表定义为一个字母表中的字母组成的一些串的集合：中的字母组成的一些串的集合：

40、 L *。 字母表上按照一定的规则定义一个文法字母表上按照一定的规则定义一个文法(grammar)，该文法所能产生的所有句子组成的集合就是该文法该文法所能产生的所有句子组成的集合就是该文法产生的语言。产生的语言。 1959年，乔姆斯基根据产生语言文法的特性，将语年，乔姆斯基根据产生语言文法的特性，将语言划分成言划分成3大类。大类。 1.4.2 形式语言与自动机理论的产生与形式语言与自动机理论的产生与作用作用 2022-3-12621951年到年到1956年，克林年，克林(Kleene) 在研究神经细胞中，在研究神经细胞中，建立了识别语言的系统建立了识别语言的系统有穷状态自动机有穷状态自动机。

41、1959年，乔姆斯基发现文法和自动机分别从生成和年，乔姆斯基发现文法和自动机分别从生成和识别的角度去表达语言，而且证明了识别的角度去表达语言，而且证明了文法与自动机文法与自动机的等价性的等价性，这一成果被认为是将形式语言置于了数，这一成果被认为是将形式语言置于了数学的光芒之下，使得形式语言真正诞生了。学的光芒之下，使得形式语言真正诞生了。 1.4.2 形式语言与自动机理论的产生与形式语言与自动机理论的产生与作用作用2022-3-126320世纪世纪50年代，巴科斯范式年代，巴科斯范式(Backus Nour Form 或或 Backus Normal Form，BNF)实现了对高级语言实现了对

42、高级语言ALGOL-60的成功描述。这一成功，使得形式语言的成功描述。这一成功，使得形式语言在在20世纪世纪60年代得到了大力的发展。尤其是上下文年代得到了大力的发展。尤其是上下文无关文法被作为计算机程序设计语言的文法的最佳无关文法被作为计算机程序设计语言的文法的最佳近似描述得到了较为深入的研究。近似描述得到了较为深入的研究。 相应的理论用于其他方面。相应的理论用于其他方面。 1.4.2 形式语言与自动机理论的产生与形式语言与自动机理论的产生与作用作用2022-3-1264形式语言与自动机理论在计算机科学与技术学科人才的形式语言与自动机理论在计算机科学与技术学科人才的计算思维的培养中占有极其重

43、要的地位。计算思维的培养中占有极其重要的地位。 计算学科的主题：计算学科的主题：“什么能被有效地自动化什么能被有效地自动化”。 1.4.2 形式语言与自动机理论的产生与形式语言与自动机理论的产生与作用作用2022-3-1265计算机科学与技术学科人才专业能力构成计算机科学与技术学科人才专业能力构成 “计算思维能力计算思维能力”抽象思维能力、逻辑思维能力。抽象思维能力、逻辑思维能力。 算法算法设计设计与分析能力与分析能力。程序设计与实现能力。程序设计与实现能力。计算机系统的认知、分析、设计和应用能力。计算机系统的认知、分析、设计和应用能力。 1.4.2 形式语言与自动机理论的产生与形式语言与自动

44、机理论的产生与作用作用2022-3-12661.4.2 形式语言与自动机理论的产生与形式语言与自动机理论的产生与作用作用2022-3-1267考虑的对象的不同，所需要的思维方式和能力就不考虑的对象的不同，所需要的思维方式和能力就不同，通过这一系统的教育，在不断升华的过程中，同，通过这一系统的教育，在不断升华的过程中，逐渐地培养出了学生的抽象思维能力和对逻辑思维逐渐地培养出了学生的抽象思维能力和对逻辑思维方法的掌握。方法的掌握。创新意识的建立和创新能力的培养也在这个教育过创新意识的建立和创新能力的培养也在这个教育过程中循序渐进地进行着。程中循序渐进地进行着。内容用于后续课程和今后的研究工作。内容

45、用于后续课程和今后的研究工作。是进行思维训练的最佳知识载体。是进行思维训练的最佳知识载体。 是一个优秀的计算机科学工作者必修的一门课程。是一个优秀的计算机科学工作者必修的一门课程。 1.4.3 基本概念基本概念 2022-3-1268对语言研究的三个方面对语言研究的三个方面 表示表示(representation) 无穷语言的表示。无穷语言的表示。 有穷描述有穷描述(finite description) 研究的语言要么是研究的语言要么是有穷的，要么是可数无穷的，这里主要研究可数无穷有穷的，要么是可数无穷的，这里主要研究可数无穷语言的有穷描述。语言的有穷描述。 结构结构(structure)语

46、言的结构特征。语言的结构特征。 1.4.3 基本概念基本概念 2022-3-1269字母表字母表(alphabet) 字母表字母表是一个非空有穷集合是一个非空有穷集合，字母表中的元素称为该字，字母表中的元素称为该字母表的一个母表的一个字母字母(letter)。又叫做。又叫做符号符号(symbol)、或者、或者字字符符(character)。非空性非空性。有穷性有穷性。例如：例如： a，b，c，d a，b，c，z 0,1 1.4.3 基本概念基本概念 2022-3-1270字符的两个特性字符的两个特性 整体性整体性(monolith)，也叫不可分性。，也叫不可分性。 可辨认性可辨认性(disti

47、nguishable)，也叫可区分性。，也叫可区分性。 例（续）例（续） a，a，b，b aa，ab，bb ， 1.4.3 基本概念基本概念 2022-3-1271字母表的乘积字母表的乘积(product) 12=ab|a1，b2 例如：例如：0,10,1=00，01，10，11 0,1a，b，c，d=0a，0b，0c，0d，1a，1b，1c，1d a，b，c，d0,1=a0，a1，b0，b1，c0，c1，d0，d1 aa，ab，bb0,1= aa0，aa1，ab0，ab1，bb0，bb1 1.4.3 基本概念基本概念 2022-3-1272字母表字母表的的n次次幂幂 0= n=n-1 是由是

48、由中的中的0个字符组成的。个字符组成的。 的的正闭包正闭包 +=234的的克林闭包克林闭包 *=0+=0231.4.3 基本概念基本概念2022-3-1273例如： 0,1+=0，1，00，01，10，11，000，001，010，011，100， 0,1*=，0，1，00，01，10，11，000，001，010，011，100， a，b，c，d+=a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，aaa，aab，aac，aad，aba，abb，abc， a，b，c，d*=，a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，aaa，aab，aac，aad，aba，

49、abb，abc, 1.4.3 基本概念基本概念2022-3-1274结论：结论：*=x|x是是中的若干个，包括中的若干个，包括0个字符，连接而成的一个个字符，连接而成的一个字符串字符串。+=x|x是是中的至少一个字符连接而成的字符串中的至少一个字符连接而成的字符串。1.4.3 基本概念基本概念2022-3-1275句子句子(sentence) (sentence) 是一个字母表，是一个字母表， x*，x叫做叫做上的一个上的一个句子。句子。句子相等。句子相等。 两个句子被称两个句子被称为为相等的，如果它相等的，如果它们对应们对应位置上的字符都位置上的字符都对应对应相相等。等。别称别称 字字(wo

50、rd)、 、(字符、符号字符、符号)行行(line)、 、(字符、符号字符、符号)串串(string)。 。1.4.3 基本概念基本概念2022-3-1276出现出现(appearance)x，y*，a，句子，句子xay中的中的a叫做叫做a在该句子中的在该句子中的一个一个出出现现。 。当当x=时，时，a的这个出现为字符串的这个出现为字符串xay的首字符的首字符 如果如果a的这个出现是字符串的这个出现是字符串xay的第的第n个字符，则个字符，则y的的首字符的这个出现是字符串首字符的这个出现是字符串xay的第的第n+1个字符。个字符。 当当y=时，时，a的这个出现是字符串的这个出现是字符串xay的

51、尾字符的尾字符例：例：abaabb。 1.4.3 基本概念基本概念2022-3-1277句子的长度句子的长度(length)(length) x x* *，句子，句子x x中字符出现的总个数叫做该中字符出现的总个数叫做该句子的句子的长长度度，记作，记作|x|x|。长度为长度为0 0的字符串叫的字符串叫空句子空句子，记作，记作。 例如：例如： |abaabb|=6 |abaabb|=6 |bbaa|=4 |bbaa|=4 | |=0|=0 |bbabaabbbaa|=11 |bbabaabbbaa|=11 1.4.3 基本概念基本概念2022-3-1278注意事项注意事项是一个句子。是一个句子。

52、 。这是因为。这是因为不是一个空集，它是含有一个空不是一个空集，它是含有一个空句子句子的集合。的集合。|=1，而，而|=0。 1.4.3 基本概念基本概念2022-3-1279并置并置(concatenation) (concatenation) x，y*，x，y的的并置并置是由串是由串x直接相接串直接相接串y所组成所组成的。记作的。记作xy。并置又叫做。并置又叫做连结连结。 。 串串x的的n次次幂幂 x0= xn=xn-1x 1.4.3 基本概念基本概念2022-3-1280例如：例如：对对x=001，y=1101 x0=y0= x4=001001001001 y4=110111011101

53、1101对对x=0101，y=110110 x2=01010101 y2=110110110110 x4=0101010101010101 y4=110110110110110110110110 1.4.3 基本概念基本概念2022-3-1281*上的上的并置运算性质并置运算性质 结合律：结合律：(xy)z=x(yz)。 左消去律：如果左消去律：如果xy=xz，则，则y=z。 右消去律：如果右消去律：如果yx=zx，则，则y=z。 唯唯一分解性：存在一分解性：存在唯唯一确定的一确定的a1，a2，an，使得使得x= a1a2an。 单位元素：单位元素：x=x=x。1.4.3 基本概念基本概念20

54、22-3-1282前缀与后缀前缀与后缀 设x，y，z，w，v*，且x=yz，w=yv (1) y是x的前缀(prefix)。(2)如果z，则y是x的真前缀(proper prefix)。(3) z是x的后缀(suffix)；(4) 如果y，则z是x的真后缀(proper suffix)。(5) y是x和w的公共前缀(common Prefix)。1.4.3 基本概念基本概念2022-3-1283公共公共前缀与后缀前缀与后缀(6)y是x和w的公共前缀，如果x和w的任何公共前缀都是y的前缀，则y是x和w的最大公共前缀。(7) 如果x=zy，w=vy，则y是x和w的公共后缀(common suffi

55、x )。(8) y是x和w的公共后缀，如果x和w的任何公共后缀都是y的后缀，则y是x和w的最大公共后缀。1.4.3 基本概念基本概念2022-3-1284例例 字母表=a，b上的句子abaabb的前缀、后缀、真前缀和真后缀如下： 前缀：，a，ab，aba，abaa，abaab，abaabb 真前缀：，a，ab，aba，abaa，abaab 后缀：，b，bb，abb，aabb，baabb，abaabb 真后缀：，b，bb，abb，aabb，baabb 1.4.3 基本概念基本概念2022-3-1285结论结论 x的任意前缀的任意前缀y有惟一的一个后缀有惟一的一个后缀z与之对应，使得与之对应，使得

56、x=yz；反之亦然。；反之亦然。 |w|w是是x的后缀的后缀|=|w|w是是x的前缀的前缀|。 w|w是是x的前缀的前缀=w|w是是x的真前缀的真前缀x， |w|w是是x的前缀的前缀|=|w|w是是x的真前缀的真前缀|+1。1.4.3 基本概念基本概念2022-3-1286结论结论 w|w是是x的后缀的后缀=w|w是是x的真后缀的真后缀x， |w|w是是x的后缀的后缀|=|w|w是是x的真后缀的真后缀|+1。 对于任意字符串对于任意字符串w，w是自身的前缀，但不是是自身的前缀，但不是自身的真前缀；自身的真前缀；w是自身的后缀，但不是自身是自身的后缀，但不是自身的真后缀。的真后缀。 对于任意字符

57、串对于任意字符串w，是是w的前缀，且是的前缀，且是w的的真前缀；真前缀；是是w的后缀，且是的后缀，且是w的真后缀的真后缀1.4.3 基本概念基本概念2022-3-1287约定约定 用小写字母表中较为靠前的字母用小写字母表中较为靠前的字母a，b，c，表表示字母表中的字母。示字母表中的字母。 用小写字母表中较为靠后的字母用小写字母表中较为靠后的字母x，y，z，表表示字母表上的句子。示字母表上的句子。 用用xT表示表示x的倒序。例如，如果的倒序。例如，如果x=abc，则，则xT=cba。 1.4.3 基本概念基本概念2022-3-1288子串子串(substring) (substring) w，x

58、，y，z*，且，且w=xyz，则称，则称y是是w的的子串。子串。公共子串公共子串( (common substring)common substring) t，u，v，w，x，y，z*，且，且t=uyv，w=xyz，则称，则称y是是t和和w的的公共子串公共子串(common substring)(common substring)。如果。如果y1，y2，yn是是t和和w的公共子串，且的公共子串，且max|y1|，|y2|，|yn|=|yj|，则称，则称yj是是t和和w的的最大公共子串。最大公共子串。 两个串的最大公共子串并不一定是惟一的。两个串的最大公共子串并不一定是惟一的。 1.4.3 基本概念基本概念2022-3-1289语言语言( (language) language) L *，L称为字母表称为字母表上的一个上的一个语语言言(language)(language)， xL，x叫做叫做L的一个句子。的一个句子。 例：例：0，1上的不同语言上的不同语言 00，11 ，0，1 0，1，00，11 ， 0，1，00，11，01，10 00，11*，01，10*，00，01，10，11*， 00，1*1