1、形式语言与自动机-经典教学课件(完整版)课程目的和基本要求课程目的和基本要求 本专业人员本专业人员4 4种基本的专业能力种基本的专业能力计算思维能力计算思维能力算法的设计与分析能力算法的设计与分析能力程序设计和实现能力程序设计和实现能力计算机软硬件系统的认知、分析、设计与应用能力计算机软硬件系统的认知、分析、设计与应用能力 计算思维能力计算思维能力逻辑思维能力和抽象思维能力逻辑思维能力和抽象思维能力构造模型对问题进行形式化描述构造模型对问题进行形式化描述理解和处理形式模型理解和处理形式模型课程目的和基本要求课程目的和基本要求 知识知识掌握正则语言、下文无关语言的文法、识别模掌握正则语言、下文无
2、关语言的文法、识别模型及其基本性质、图灵机的基本知识。型及其基本性质、图灵机的基本知识。 能力能力培养学生的形式化描述和抽象思维能力。培养学生的形式化描述和抽象思维能力。使学生了解和初步掌握使学生了解和初步掌握“问题、形式化描述、问题、形式化描述、自动化（计算机化）自动化（计算机化）”这一最典型的计算机问这一最典型的计算机问题求解思路。题求解思路。 主要内容主要内容 语言的语言的文法文法描述。描述。 RL RG、 FA、RE、RL的性质的性质 。 CFL CFG(CNF、GNF)、PDA、CFL的性质。的性质。 TM 基本基本TM、构造技术、构造技术、TM的修改。的修改。 CSL CSG、LB
3、A。教材及主要参考书目教材及主要参考书目 蒋宗礼，姜守旭蒋宗礼，姜守旭. 形式语言与自动机理论形式语言与自动机理论. 北京：北京：清华大学出版社，清华大学出版社，2003年年 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. Introductio
4、n to Automata Theory, Languages, and Computation. Addison-Wesley Publishing Company, 1979第第1章章 绪论绪论1.1 集合的基础知识集合的基础知识 1.1.1 集合及其表示集合及其表示 集合：一定范围内的、确定的、并且彼此可以区集合：一定范围内的、确定的、并且彼此可以区分的对象汇集在一起形成的整体叫做分的对象汇集在一起形成的整体叫做集合集合(set)，简称为集简称为集(set)。 元素：集合的成员为该集合的元素：集合的成员为该集合的元素元素(element)。 集合描述形式。集合描述形式。 基数。基数。 集
5、合的分类。集合的分类。 1.1.2 集合之间的关系集合之间的关系 子集子集 如果集合如果集合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 集合之间的关系集合之间的关系集合相等集合相
6、等 如果集合如果集合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 集合之间的关系集合之间的关系 如果如果A B，则对，则对 xA，有，有xB。如果如果A B，则对，则对 xA，有，有xB并且并且 xB，但，但x A。 如果如果A B且且B C，则，则A C。 如果如果A B且且B C，或者，或者A
7、B且且B C，或者，或者A B且且B C，则，则A C。 如果如果A=B，则，则|A|=|B|。1.1.3 集合的运算集合的运算 并并(union) A与与B的的并并(union)是一个集合，该集合中的元素要么是一个集合，该集合中的元素要么是是A的元素，要么是的元素，要么是B的元素，记作的元素，记作AB。 AB=a|aA或者或者aB A1A2An=a| i，1in，使得，使得aAi A1A2An =a| i，iN,使得使得aAi1iiA,|AaSAaASA交交(intersection) 集合集合A和和B中都有的所有元素放在一起构成中都有的所有元素放在一起构成的集合为的集合为A与与B的的交交
8、，记作，记作AB。 AB=a|aA且且aB “”为交运算符，为交运算符，AB读作读作A交交B。 如果如果AB=，则称，则称A与与B不相交。不相交。 AB= BA。 (AB)C=A(BC)。 AA=A。交交(intersection) 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) 属于属于A，但不属于，但不属于B的所有元素组成的集合叫做的所有元素组成的集合叫做A与与B的的差，记作差，记作A-B。 A-B=a|aA且且a B “-”为减为减(差差)运
9、算符，运算符，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) 属于属于A但不属于但不属于B，属于，属于B但不属于但不属于A的所有元的所有元素组成的集合叫素组成的集合叫A与与B的的对称差，记作对称差，记作ABAB。 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)-
10、(AB)=(A-B)(B-A)。 笛卡儿积笛卡儿积(Cartesian product) A与与B的的笛卡儿积笛卡儿积(Cartesian product)是一个集合，是一个集合，该集合是由所有这样的有序对该集合是由所有这样的有序对(a，b)组成的：其组成的：其中中aA，bB ，记作，记作AB。 AB=(a，b)|aA& bB 。 “”为笛卡儿乘运算符。为笛卡儿乘运算符。AB读作读作A叉乘叉乘B。 ABBA。 (AB)CA(BC)。 AAA。 A=。笛卡儿积笛卡儿积(Cartesian product) A(BC)=(AB)(AC)。 (BC)A=(BA)(AC)。 A(BC)=(AB)(AC
11、)。 (BC)A=(BA)(CA)。 A(B-C)=(AB)-(AC)。 (B-C)A=(BA)-(CA)。 当当A、B为有穷集时，为有穷集时，|AB|=|A|*|B|。 幂集幂集(power set) A幂集幂集(power set)是一个集合，该集合是是一个集合，该集合是由由A的所有子集组成的，记作的所有子集组成的，记作2A。 2A=B|B A。 2A读作读作A的幂集。的幂集。幂集幂集(power set) 2A。 2A。 2A。 2=。 A2A。 如果如果A是有穷集，则是有穷集，则|2A|=2|A|。 2AB=2A2B。 如果如果A B，则，则2A 2B。 补集补集(complement
12、ary set) A是论域U上的一个集合，A补集补集是由U中的、不在A中的所有元素组成的集合，记作AUAUU补集补集(complementary set)AABAUBAAB&BABABABAAB UAA如果如果A B，则，则。1.2 关系关系 二元关系二元关系 递归定义与归纳证明递归定义与归纳证明 关系的闭包关系的闭包 1.2.1 二元关系二元关系(binary relation) 二元关系二元关系 任意的RAB，R是A到B的二元关系。二元关系。 (a，b) R，也可表示为：aRb。 A称为定义域定义域(domain)，B称为值域值域(range)。 当A=B时，则称R是A上的二元关系。 二元
13、关系的性质二元关系的性质 自反(reflexive)性、反自反(irreflexive)性、对称(symmetric)性、反对称(asymmetric)性、传递(transitive)性。1.2.1 二元关系二元关系(binary relation) 三歧性三歧性 自反性、对称性、传递性。自反性、对称性、传递性。 等价关系等价关系(equivalence relation) 具有三歧性的二元关系称为等价关系。等价关系。 1.2.1 二元关系二元关系(binary relation) 等价类等价类 (equivalence class) S的满足如下要求的划分：的满足如下要求的划分：S1、S2、
14、S3、Sn称称为为S关于关于R的等价划分，的等价划分，Si称为等价类。称为等价类。 S= S1S2S3Sn； 如果如果ij，则，则SiSj=； 对任意的对任意的i，Si中的任意两个元素中的任意两个元素a、b，aRb恒成恒成立；立； 对任意的对任意的i，j，ij，Si中的任意元素中的任意元素a和和Sj中的任中的任意元素意元素b，aRb恒不成立恒不成立 1.2.1 二元关系二元关系(binary relation) 指数指数(index) 把把R将将S分成的等价类的个数称为是分成的等价类的个数称为是R在在S上的上的指数指数。如果。如果R将将S分成有穷多个等价类，则称分成有穷多个等价类，则称R具有有
15、穷指数；如果具有有穷指数；如果R将将S分成无穷多个等价类，分成无穷多个等价类，则称则称R具有无穷指数。具有无穷指数。 给定集合给定集合S上的一个等价关系上的一个等价关系R，R就确定了就确定了S的一个等价分类，当给定另一个不同的等价关的一个等价分类，当给定另一个不同的等价关系时，它会确定系时，它会确定S的一个新的等价分类。的一个新的等价分类。 1.2.1 二元关系二元关系(binary relation) 关系的合成关系的合成 (composition) 设设R1 AB是是A到到B的关系、的关系、R2 BC是是B到到C的关系，的关系，R1与与R2的的合成合成R1R2是是A到到C的关系：的关系：R
16、1R2=(a，c)| (a，b) R1且且(b，c) R2 。 1.2.1 二元关系二元关系(binary relation) R1R2R2R1。 (R1R2)R3=R1(R2R3)。 (结合率结合率) (R1R2)R3=R1R3R2R3。(右分配率右分配率) R3(R1R2)=R3R1R3R2。(左分配率左分配率) (R1R2)R3 R1R3R2R3。 R3(R1R2) R3R1R3R2。1.2.1 二元关系二元关系(binary relation)关系这一个概念用来反映对象关系这一个概念用来反映对象集合元集合元素之间的联系和性质素之间的联系和性质二元关系则是反映两个元素之间的关系，二元关系
17、则是反映两个元素之间的关系，包括某个元素的某种属性。包括某个元素的某种属性。对二元关系的性质，要强调全称量词是对对二元关系的性质，要强调全称量词是对什么样的范围而言的。什么样的范围而言的。1.2.2 等价关系与等价类等价关系与等价类（略）1.2.3 关系的合成关系的合成（略） 1.2.4 递归定义与归纳证明递归定义与归纳证明 递归定义(recursive definition) 又称为归纳定义(inductive definition)，它来定义一个集合。 集合的递归定义由三部分组成： 基础(basis)：用来定义该集合的最基本的元素。 归纳(induction)：指出用集合中的元素来构造集合
18、的新元素的规则。 极小性限定：指出一个对象是所定义集合中的元素的充要条件是它可以通过有限次的使用基础和归纳条款中所给的规定构造出来。 1.2.4 递归定义与归纳证明递归定义与归纳证明 归纳证明归纳证明 与递归定义相对应。与递归定义相对应。 归纳证明方法包括三大步：归纳证明方法包括三大步： 基础基础(basis)：证明最基本元素具有相应性质。：证明最基本元素具有相应性质。 归纳归纳(induction)：证明如果某些元素具有相：证明如果某些元素具有相应性质，则根据这些元素用所规定的方法得应性质，则根据这些元素用所规定的方法得到的新元素也具有相应的性质。到的新元素也具有相应的性质。 根据归纳法原理
19、，所有的元素具有相应的性根据归纳法原理，所有的元素具有相应的性质。质。 1.2.4 递归定义与归纳证明递归定义与归纳证明 定义定义 1-17 设设R是是S上的关系，我们递归地定义上的关系，我们递归地定义Rn的幂：的幂： R0=(a，a)|aS。 Ri=Ri-1R (i=1,2,3,4,5,)。1.2.4 递归定义与归纳证明递归定义与归纳证明 例例1-17 著名的斐波那契著名的斐波那契(Fibonacci)数的定义数的定义 基础：基础：0是第一个斐波那契数，是第一个斐波那契数，1第二个斐波第二个斐波那契数；那契数； 归纳：如果归纳：如果n是第是第i个斐波那契数，个斐波那契数，m是第是第i+1个斐
20、波那契数，则个斐波那契数，则n+m是第是第i+2个斐波那契数，个斐波那契数，这里这里i为大于等于为大于等于1的正整数。的正整数。 只有满足只有满足(1)和和(2)的数才是斐波那契数的数才是斐波那契数 0，1，1，2，3，5，8，13，21，34，55，1.2.4 递归定义与归纳证明递归定义与归纳证明例例1-18 算术表达式算术表达式 基础：常数是算术表达式，变量是算术表基础：常数是算术表达式，变量是算术表达式；达式； 归纳：如果归纳：如果E1、E2是表达式，则是表达式，则 +E1、-E1、E1+E2、 E1-E2 、E1*E2 、E1/E2、E1*E2、Fun(E1)是算术表达式。其中是算术表
21、达式。其中Fun为函数名。为函数名。 只有满足只有满足(1)和和(2)的才是算术表达式。的才是算术表达式。 1.2.4 递归定义与归纳证明递归定义与归纳证明 例例1-19 对有穷集合对有穷集合A，证明，证明|2A|=2|A|。证明：证明：设设A为一个有穷集合为一个有穷集合, 施归纳于施归纳于|A|： 基础：当基础：当|A|=0时时,|2A|=|=1。 归纳：假设归纳：假设|A|=n时结论成立，这里时结论成立，这里n 0，往证当往证当|A|=n+1时结论成立时结论成立 2A=2BCa|C2B 2BCa|C2B= 1.2.4 递归定义与归纳证明递归定义与归纳证明 |2A|=|2BCa|C2B|=|
22、2B|+|Ca|C2B|=|2B|+|2B|=2*|2B|=2*2|B|=2|B|+1=2|A| 由归纳法原理，结论对任意有穷集合成立。由归纳法原理，结论对任意有穷集合成立。1.2.4 递归定义与归纳证明递归定义与归纳证明例例1-20 表达式的前缀形式是指将运算符表达式的前缀形式是指将运算符写在前面，后跟相应的运算对象。如：写在前面，后跟相应的运算对象。如：+E1的的前缀形式为前缀形式为+E1，E1+E2的前缀形式为的前缀形式为+E1E2 ，E1*E2的前缀形式为的前缀形式为*E1E2， E1*E2的前缀形的前缀形式为式为* E1，Fun(E1) 的前缀形式为的前缀形式为FunE1 。证明例证
23、明例1-18所定义的表达式可以用这里定所定义的表达式可以用这里定义的前缀形式表示。义的前缀形式表示。 1.2.4 递归定义与归纳证明递归定义与归纳证明 递归定义给出的概念有利于归纳证明。在递归定义给出的概念有利于归纳证明。在计算机科学与技术学科中，有许多问题可计算机科学与技术学科中，有许多问题可以用递归定义描述或者用归纳方法进行证以用递归定义描述或者用归纳方法进行证明，而且在许多时候，这样做会带来许多明，而且在许多时候，这样做会带来许多方便。方便。 主要是掌握主要是掌握递归定义与归纳证明递归定义与归纳证明的叙述格的叙述格式。式。 1.2.5 关系的闭包关系的闭包 闭包闭包(closure) 设
24、设P是关于关系的性质的集合，关系是关于关系的性质的集合，关系R的的P闭包闭包(closure)是包含是包含R并且具有并且具有P中所有性质的最中所有性质的最小关系小关系。 正闭包正闭包(positive closure) (1)R R+。(2)如果如果(a，b)，(b，c)R+ 则则(a，c)R+。(3)除除(1)、(2)外，外，R+不再含有其他任何元素不再含有其他任何元素。 1.2.5 关系的闭包关系的闭包传递闭包传递闭包(transitive closure) 具有传递性的闭包。具有传递性的闭包。 R+具有传递性。具有传递性。可以证明，对任意二元关系可以证明，对任意二元关系R， R+= RR
25、2R3R4而且当而且当S为有穷集时：为有穷集时： R+= RR2R3R|S|1.2.5 关系的闭包关系的闭包克林闭包克林闭包(Kleene 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 closure) R*具有自反性、传递性具有自反性、传递性。1.2.5 关系的闭包关系的闭包
26、可以证明，对任意二元关系可以证明，对任意二元关系R， R*= R0R+ R* =R0RR2R3R4 而且当而且当S为有穷集时：为有穷集时： R*= R0RR2R3R|S| 1.2.5 关系的闭包关系的闭包 R1、R2是是S上的两个二元关系上的两个二元关系 (1) +=。 (2) (R1+)+= R1+ 。 (3) (R1*)*= R1*。 (4) R1+R2+ (R1R2)+。 (5) R1*R2* (R1R2)*。 1.3 图图 数学家欧拉数学家欧拉(L.Euler)解决著名的哥尼斯堡解决著名的哥尼斯堡七桥。七桥。 直观地讲，图是由一些点和一些连接两点直观地讲，图是由一些点和一些连接两点的边
27、组成。的边组成。 含无方向的边的图为无向图，含带有方向含无方向的边的图为无向图，含带有方向的边的图为有向图。的边的图为有向图。 1.3.1 无向图无向图 无向图无向图(undirected graph) 设设V是一个非空的有穷集合，是一个非空的有穷集合，E VV，G=(V，E)称为称为无向图无向图(undirected graph)。其中。其中V中的中的元素称为元素称为顶点顶点(vertex或或node)，V称为顶点集，称为顶点集，E中的元素称为中的元素称为无向边无向边(undirected edge)，E为为无向边集。无向边集。 图表示图表示 V中称为顶点中称为顶点v的元素用标记为的元素用标
28、记为v的小圈表示，的小圈表示，E中的元素中的元素(v1，v2)用标记为用标记为v1，v2的顶点之间的的顶点之间的连线表示。连线表示。 1.3.1 无向图无向图 路路(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 无向图无向图 顶点的度数顶点的度数 对于对于vV，|v|(v，w)E|称为无向图称为无向图G=(V，E)的顶点的顶点v的度
29、数，记作的度数，记作deg(v)。 对于任何一个图，图中所有顶点的度数之和为对于任何一个图，图中所有顶点的度数之和为图中边的图中边的2倍。倍。 VvEv|*2)deg(deg(v1)=3deg(v2)=3deg(v3)=4deg(v4)=3deg(v5)=3deg(v1)+deg(v2)+deg(v3)+deg(v4)+deg(v5)=16 1.3.1 无向图无向图 连通图连通图 如果对于如果对于 v，wV，vw，v与与w之间至少有之间至少有一条路存在，则称一条路存在，则称G=(V，E)是是连通图连通图。 图图G是连通的充要条件是是连通的充要条件是G中存在一条包含图中存在一条包含图的所有顶点的
30、路。的所有顶点的路。 1.3.2 有向图有向图 有向图有向图(directed graph) G=(V，E)。 V：顶点顶点(vertex或或node)集。集。 (v1，v2)E：顶点顶点v1到顶点到顶点v2的的有向边有向边(directed edge)，或，或弧弧(arc)，v1称为称为前导前导(predecessor)，v2称为称为后继后继(successor)。 有向路有向路(directed path) 如果对于如果对于0ik-1，k1，均有，均有(vi，vi+1)E，则称则称v0，v1，vk是是G的一条长为的一条长为k的的有向路。有向路。 1.3.2 有向图有向图 有向回路或有向圈有
31、向回路或有向圈(directed cycle) 对于对于0ik-1，k1，均有，均有(vi，vi+1)E， 且且v0=vk，则称，则称v0，v1，vk是是G的一条长为的一条长为k的的有向路为有向路为一个一个有向回路。有向回路。 有向回路又叫有向圈。有向回路又叫有向圈。 有向图的图表示有向图的图表示图图G G的图表示是满足下列条件的的图表示是满足下列条件的“图图”：其中：其中V V中称为顶点中称为顶点v v的元素用标记为的元素用标记为v v的小圈表示，的小圈表示，E E中的元素中的元素(v(v1 1，v v2 2) )用从标记为用从标记为v v1 1的顶点到标记的顶点到标记为为v v2 2的顶点
32、的弧表示。的顶点的弧表示。 1.3.2 有向图有向图 顶点的度数顶点的度数 入度入度(数数)：ideg(v)=|v|(w，v)E|。 出度出度(数数)：odeg(v)= |v|(v，w)E|。 对于任何一个有向图，图中所有顶点的入对于任何一个有向图，图中所有顶点的入度之和与图中所有顶点的出度之和正好是度之和与图中所有顶点的出度之和正好是图中边的个数图中边的个数 VvVvEvovi|)deg()deg(两个不同的有向图两个不同的有向图1.3.3 树树 满足如下条件的有向图满足如下条件的有向图G=(V，E)称为一棵称为一棵(有序、有向有序、有向)树树(tree)： 根根(root) v：没有前导，
33、且没有前导，且v到树中其他顶点均到树中其他顶点均有一条有向路。有一条有向路。每个非根顶点有且仅有一个前导。每个非根顶点有且仅有一个前导。 每个顶点的后继按其拓扑关系从左到右排序。每个顶点的后继按其拓扑关系从左到右排序。 1.3.3 树树 树的基本概念树的基本概念 (1) 顶点也可以成为结点。顶点也可以成为结点。(2) 结点的前导为该结点的结点的前导为该结点的父亲父亲(父结点父结点father)。(3) 结点的后继为它的结点的后继为它的儿子儿子(son)。(4) 如果树中有一条从结点如果树中有一条从结点v1到结点到结点v2的路，则称的路，则称v1是是v2的的祖先祖先(ancestor), v2是
34、是v1的的后代后代(descendant)。(5) 无儿子的顶点叫做无儿子的顶点叫做叶子叶子(leaf)。(6) 非叶结点叫做非叶结点叫做中间结点中间结点(interior)。1.3.3 树树 树的层树的层 根处在树的第根处在树的第1层层(level)。 如果结点如果结点v处在第处在第i层层(i1)，则，则v的儿子处在第的儿子处在第i+1层层。树的最大层号叫做该树的高度树的最大层号叫做该树的高度(height)。 1.3.3 树树 二元树二元树 如果对于如果对于 vV，v最多只有最多只有2个儿子，则称个儿子，则称G=(V，E)为为二元树二元树(binary tree)。 对一棵二元树，它的第对
35、一棵二元树，它的第n层最多有层最多有2n-1个结点。个结点。一棵一棵n层二元树最多有个层二元树最多有个2n-1叶子。叶子。 1.4 语言语言 1.4.1 什么是语言什么是语言 例如：例如：“学大一生是个我学大一生是个我”；“我是一我是一个大学生个大学生”。 语言是一定的群体用来进行交流的工具。语言是一定的群体用来进行交流的工具。 必须有着一系列的生成规则、理解必须有着一系列的生成规则、理解(语义语义)规则规则。1.4.1 什么是语言什么是语言 1.4.1 什么是语言什么是语言 斯大林：从强调语言的作用出发，把语言斯大林：从强调语言的作用出发，把语言定义为定义为“为广大的人群所理解的字和组合为广
36、大的人群所理解的字和组合这些字的方法这些字的方法”。 语言学家韦波斯特语言学家韦波斯特(Webster) ：为相当大的：为相当大的团体的人所懂得并使用的字和组合这些字团体的人所懂得并使用的字和组合这些字的方法的统一体。的方法的统一体。 要想对语言的性质进行研究，用这些定义要想对语言的性质进行研究，用这些定义来建立语言的数学模型是不够精确的。必来建立语言的数学模型是不够精确的。必须有更形式化的定义。须有更形式化的定义。 1.4.2 形式语言与自动机理论的形式语言与自动机理论的产生与作用产生与作用 语言学家乔姆斯基，毕业于宾西法尼亚大语言学家乔姆斯基，毕业于宾西法尼亚大学，最初从产生语言的角度研究
37、语言。学，最初从产生语言的角度研究语言。1956年，他将语言年，他将语言L定义为一个字母表定义为一个字母表中中的字母组成的一些串的集合：的字母组成的一些串的集合： L *。 字母表上按照一定的规则定义一个文法字母表上按照一定的规则定义一个文法(grammar)，该文法所能产生的所有句子组，该文法所能产生的所有句子组成的集合就是该文法产生的语言。成的集合就是该文法产生的语言。 1959年，乔姆斯基根据产生语言文法的特年，乔姆斯基根据产生语言文法的特性，将语言划分成性，将语言划分成3大类。大类。 1.4.2 形式语言与自动机理论的形式语言与自动机理论的产生与作用产生与作用 1951年到年到1956
38、年，克林年，克林(Kleene) 在研究神经在研究神经细胞中，建立了识别语言的系统细胞中，建立了识别语言的系统有穷有穷状态自动机。状态自动机。 1959年，乔姆斯基发现文法和自动机分别年，乔姆斯基发现文法和自动机分别从生成和识别的角度去表达语言，而且证从生成和识别的角度去表达语言，而且证明了文法与自动机的等价性，这一成果被明了文法与自动机的等价性，这一成果被认为是将形式语言置于了数学的光芒之下，认为是将形式语言置于了数学的光芒之下，使得形式语言真正诞生了。使得形式语言真正诞生了。 1.4.2 形式语言与自动机理论的形式语言与自动机理论的产生与作用产生与作用 20世纪世纪50年代，巴科斯范式年代
39、，巴科斯范式(Backus Nour Form 或或 Backus Normal Form，BNF)实现实现了对高级语言了对高级语言ALGOL-60的成功描述。这的成功描述。这一成功，使得形式语言在一成功，使得形式语言在20世纪世纪60年代得年代得到了大力的发展。尤其是上下文无关文法到了大力的发展。尤其是上下文无关文法被作为计算机程序设计语言的文法的最佳被作为计算机程序设计语言的文法的最佳近似描述得到了较为深入的研究。近似描述得到了较为深入的研究。 相应的理论用于其他方面。相应的理论用于其他方面。 1.4.2 形式语言与自动机理论的形式语言与自动机理论的产生与作用产生与作用 形式语言与自动机理
40、论在计算机科学与技术形式语言与自动机理论在计算机科学与技术学科的人才的计算思维的培养中占有极其重学科的人才的计算思维的培养中占有极其重要的地位。要的地位。 计算学科的主题：计算学科的主题：“什么能被有效地自动什么能被有效地自动化化”。 1.4.2 形式语言与自动机理论的形式语言与自动机理论的产生与作用产生与作用 计算机科学与技术学科人才专业能力构成计算机科学与技术学科人才专业能力构成 “计算思维能力计算思维能力”抽象思维能力、逻辑思抽象思维能力、逻辑思维能力。维能力。 算法设计与分析能力。算法设计与分析能力。 程序设计与实现能力。程序设计与实现能力。计算机系统的认知、分析、设计和应用能力。计算
41、机系统的认知、分析、设计和应用能力。 1.4.2 形式语言与自动机理论的形式语言与自动机理论的产生与作用产生与作用1.4.2 形式语言与自动机理论的形式语言与自动机理论的产生与作用产生与作用考虑的对象的不同，所需要的思维方式和能力就不考虑的对象的不同，所需要的思维方式和能力就不同，通过这一系统的教育，在不断升华的过程中，同，通过这一系统的教育，在不断升华的过程中，逐渐地培养出了学生的抽象思维能力和对逻辑思维逐渐地培养出了学生的抽象思维能力和对逻辑思维方法的掌握。方法的掌握。创新意识的建立和创新能力的培养也在这个教育过创新意识的建立和创新能力的培养也在这个教育过程中循序渐进地进行着。程中循序渐进
42、地进行着。内容用于后续课程和今后的研究工作。内容用于后续课程和今后的研究工作。是进行思维训练的最佳知识载体。是进行思维训练的最佳知识载体。 是一个优秀的计算机科学工作者必修的一门课程。是一个优秀的计算机科学工作者必修的一门课程。 1.4.3 基本概念基本概念 对语言研究的三个方面对语言研究的三个方面 表示表示(representation) 无穷语言的表示。无穷语言的表示。 有穷描述有穷描述(finite description) 研究的语言要研究的语言要么是有穷的，要么是可数无穷的，这里主要研么是有穷的，要么是可数无穷的，这里主要研究可数无穷语言的有穷描述。究可数无穷语言的有穷描述。 结构结
43、构(structure)语言的结构特征。语言的结构特征。 1.4.3 基本概念基本概念 字母表字母表(alphabet) 字母表字母表是一个非空有穷集合，字母表中的元素是一个非空有穷集合，字母表中的元素称为该字母表的一个称为该字母表的一个字母字母(letter)。又叫做。又叫做符号符号(symbol)、或者、或者字符字符(character)。 非空性。非空性。 有穷性。有穷性。 例如：例如： a，b，c，d a，b，c，z 0,1 1.4.3 基本概念基本概念 字符的两个特性字符的两个特性 整体性整体性(monolith)，也叫不可分性。，也叫不可分性。 可辨认性可辨认性(distingui
44、shable)，也叫可区分性。，也叫可区分性。 例（续）例（续） a，a，b，b aa，ab，bb ， 1.4.3 基本概念基本概念 字母表的乘积字母表的乘积(product) 12=ab|a1，b2 例如：例如：0,10,1=00，01，10，00 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 基本概念基本概念 字母表字母表的的n次次幂幂 0= n=n-1 是由是由中的中的0个字符组成的。个字符组成的。 的的正闭包
45、正闭包 +=234 的的克林闭包克林闭包 *=0+=0231.4.3 基本概念基本概念 例如： 0,1+=0，1，00，01，11，000，001，010，011，100， 0,1*=，0，1，00，01，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，abb，abc, 1.4.3 基本概念基本概念 结论：结论：*=x|x是是中的若干
46、个，包括中的若干个，包括0个字符，连接个字符，连接而成的一个字符串而成的一个字符串。+=x|x是是中的至少一个字符连接而成的字符中的至少一个字符连接而成的字符串串。1.4.3 基本概念基本概念 句子句子(sentence) 是一个字母表，是一个字母表， x*，x叫做叫做上的一个上的一个句子。句子。 句子相等。句子相等。 两个句子被称为相等的，如果它们对应位置上的字两个句子被称为相等的，如果它们对应位置上的字符都对应相等。符都对应相等。 别称别称 字字(word)、(字符、符号字符、符号)行行(line)、(字符、符号字符、符号)串串(string)。1.4.3 基本概念基本概念 出现出现(ap
47、perance) x，y*，a，句子，句子xay中的中的a叫做叫做a在该句在该句子中的一个子中的一个出现。出现。 当当x=时，时，a的这个出现为字符串的这个出现为字符串xay的首字符的首字符 如果如果a的这个出现是字符串的这个出现是字符串xay的第的第n个字符，个字符，则则y的首字符的这个出现是字符串的首字符的这个出现是字符串xay的第的第n+1个字符。个字符。 当当y=时，时，a的这个出现是字符串的这个出现是字符串xay的尾字符的尾字符 例：例：abaabb。 1.4.3 基本概念基本概念 句子的长度句子的长度(length) x*，句子，句子x中字符出现的总个数叫做该中字符出现的总个数叫做
48、该句句子的长度子的长度，记作，记作|x|。 长度为长度为0的字符串叫的字符串叫空句子空句子，记作，记作。 例如：例如： |abaabb|=6 |bbaa|=4 |=0 |bbabaabbbaa|=11 1.4.3 基本概念基本概念 注意事项注意事项 是一个句子。是一个句子。 。这是因为。这是因为不是一个空集，它是含有不是一个空集，它是含有一个空句子一个空句子的集合。的集合。|=1，而，而|=0。 1.4.3 基本概念基本概念 并置并置(concatenation) x，y*，x，y的的并置并置是由串是由串x直接相接串直接相接串y所所组成的。记作组成的。记作xy。并置又叫做。并置又叫做连结。连结
49、。 串串x的的n次次幂幂 x0= xn=xn-1x 1.4.3 基本概念基本概念 例例如：如： 对对x=001，y=1101 x0=y0= x4=001001001001 y4=1101110111011101 对对x=0101，y=110110 x2=01010101 y2=110110110110 x4=0101010101010101 y4=110110110110110110110110 1.4.3 基本概念基本概念 *上的并置运算性质上的并置运算性质 结合律：结合律：(xy)z=x(yz)。 左消去律：如果左消去律：如果xy=xz，则，则y=z。 右消去律：如果右消去律：如果yx=z
50、x，则，则y=z。 惟一分解性：存在惟一确定的惟一分解性：存在惟一确定的a1，a2，an，使得，使得x= a1a2an。 单位元素：单位元素：x=x=x。1.4.3 基本概念基本概念前缀与后缀前缀与后缀 设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 基本概念基本概念公共公共前缀与后缀前缀与后缀(6)如果x和w的任何公共前缀都
