有限自动机理论ch

《有限自动机理论ch》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、有限自动机理论06016004陈文宇电子科技大学计算机科学与工程学院联系方式cwy@uestc.edu.cn13808181782B1-513学时：４０（前8周）学分：２考试：闭卷、笔试考查：作业(3-4次)，不参加考试教材：有限自动机理论陈文宇电子科技大学出版社2007.3参考书形式语言与自动机理论(第2版)（蒋宗礼姜守旭清华大学出版社）形式语言与自动机（陈有祺机械工业出版社）参考书IntroductiontoAutomataTheory,Languages,andComputation(SecondEdition)自动机理论、语言和计算导论（JohnE.H

2、opcroft清华大学出版社）理论来源形式语言和自动机的理论来源于(1)Chomsky对自然语言的研究；(2)ALGOL60语言的语法描述方式；(3)Turing、Kleene、Neumann、Huffman等对自动机的研究。形式语言与自动机的作用形式语言和自动机的理论已经成为计算机科学的理论基础。应用范围已被扩展到生物工程、自动控制系统、图象处理与模式识别等许多领域。计算机学科的专业能力计算思维能力算法设计与分析能力程序设计与实现能力计算机系统的认知、分析、设计和运用能力计算(机)思维能力形式化描述能力抽象思维能力逻辑思维方法相关理论是计算机学科基础。理论方

3、面的知识是计算机科学的真正灵魂。这也是计算机科学与其他学科的重要区别。有限自动机理论在科学领域中得到直接应用对于计算机科学人才的计算思维能力的培养，也具有重要作用。在本科阶段,以观察、描述、比较分类、推断、应用的科学思维过程为主。研究生阶段，需要进一步进行抽象思维、逻辑思维、创造思维能力的培养。本科生与研究生的根本区别在于研究生的需要宽厚、坚实的理论知识。第1章基础知识本章将对有限自动机理论中所需的数学基础知识作扼要的介绍。包括集合及其运算、关系、证明的方法、图与树的概念；以及一些常用术语和形式语言与自动机的发展。内容：1.1集合及其运算1.2关系1.3证明和

4、证明的方法1.4图与树1.5语言1.6常用术语1.7形式语言与自动机的发展1.1集合及其运算一些没有重复的对象的全体称为集合，而这些被包含的对象称为该集合的元素。集合中元素可以按任意的顺序进行排列。使用大写英文字母表示一个集合。有穷集合和无穷集合如果一个集合包含的元素个数是有限的，称该集合为有穷集合。如果一个集合包含的元素是无限的，称该集合为无穷集合。无穷集合又分为可数集(如正奇数集)和不可数集(如实数集)。集合的定义方法：列举法命题法列举法(穷举法)对于有穷的，且元素个数较少的集合，可以采用列举法，即将集合的所有元素全部列出，并放在一对花括号中。例集合A={

5、1，2，3，4，5}对于某些无穷集合，也可以使用类似列举的方法进行描述如自然数集合：{0，1，2，3，…}命题法对于集合元素较多的有穷集合或者是无穷集合，可使用集合元素的形成模式{x

6、P(x)}进行描述。其中：x表示集合中的任一元素,P(x)是一个谓词，对x进行限定。{x

7、P(x)}表示由满足P(x)的一切x构成的集合。可以使用自然语言，或者数学表示法来描述谓词P(x)。例如：{n

8、n是偶数}或{n

9、nmod2=0}表明了由所有偶数组成的集合。集合的基数若集合A包含元素x，记为xA反之，xA对于有穷集合A，使用

10、A

11、表示该集合包含的元素的个数，也称基数或势

12、

13、A

14、=0A=Ø。定义1-1子集设A,B是两个集合，如果集合A中的每个元素都是集合B的元素，则称集合A是集合B的子集(集合B是集合A的包集)AB或BAA,B是两个集合，如果AB，且xB，但xA，则称A是B的真子集AB两个集合相等，当且仅当AB且BA注意：不是AB且BA定义1-2集合的运算集合A与集合B的并，记为A∪B。集合A的所有元素和集合B的所有元素合并在一起组成的集合。A∪B={x

15、x∈A或x∈B}思考：什么情况下：A∪B=A？集合A与集合B的交，记为A∩B是由集合A和集合B的所有公共元素组成的集合。A∩B={x

16、x∈A且x∈B}思

17、考：什么情况下：A∩B=A？集合A与集合B的差，记为AB属于集合A但不属于集合B的所有元素组成的集合。AB={x

18、x∈A且xB}思考:什么情况下：A-B=A？如果BA，将AB称为集合B（关于集合A）的补。集合A称为集合B的全集（或论域）定义1-3幂集设A为一个集合，那么A的幂集为A的所有子集组成的集合记为2A2A={B

19、BA}例1-1集合A={1，2，3}，则A的幂集为:2A={Ø，{1}，{2}，{3}，{1，2}，{1，3}，{2，3}，{1，2，3}}幂集2A的元素个数当集合A为有穷集时，如果

20、A

21、=n，那么A的幂集2A的元素个数(集合A的所

22、有子集的个数)为2n。（集合A的幂集表