资源描述：
《形式语言与自动机 -讲稿-5》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、形式语言与自动机理论FormalLanguagesandAutomataTheory课程目的和基本要求▪课程性质技术基础▪基础知识要求数学分析（或者高等数学），离散数学▪主要特点抽象和形式化理论证明和构造性基本模型的建立与性质▪本专业人员4种基本的专业能力计算思维能力算法的设计与分析能力程序设计和实现能力计算机软硬件系统的认知、分析、设计与应用能力▪计算思维能力逻辑思维能力和抽象思维能力构造模型对问题进行形式化描述理解和处理形式模型▪知识掌握正则语言、上下文无关语言的文法、识别模型及其基本性质、图灵机的基本知识。▪能力培养学生的
2、形式化描述和抽象思维能力。使学生了解和初步掌握“问题、形式化描述、自动化（计算机化）”这一最典型的计算机问题求解思路。主要内容▪语言的文法描述。▪RL（RegularLanguage正则语言）RG（RegularGrammar正则文法）、FA（FiniteAutomation有穷状态自动机）、RE（RegularExpression正则表达式）、RL的性质。▪CFL（ContextFreeLanguage上下文无关语言）CFL–CFG(CNF、GNF)、PDA、CFL的性质。CFG（ContextFreeGrammar上下文无关
3、文法）CNF（ChomskyNormalForm乔姆斯基范式）GNF（GreibachNormalForm格雷巴赫范式）76PDA（PushdownAutomation下推自动机）▪TM（TuringMachine图灵机）基本TM、构造技术、TM的修改。CSL（ContextSensitiveLanguage上下文有关语言）CSG（ContextSensitiveGrammar上下文有关文法）、LBA（LinearBoundedAutomation线性有界自动机）。教材及主要参考书目[1]蒋宗礼，姜守旭.形式语言与自动机理论.北
4、京：清华大学出版社，2003年[2]JohnE.Hopcroft,RajeevMotwani,JeffreyD.Ullman.自动机理论、语言和计算导论（原书第三版）.北京:机械工业出版社,2008.JohnE.Hopcroft;RajeevMotwani;JeffreyD.Ullman.IntroductiontoAutomataTheory,Languages,andComputation(3rdEdition).Addison-WesleyPublishingCompany,2006[3]ThomasA.Sudkamp.语
5、言与机器:计算机科学理论导论（原书第三版）.北京:机械工业出版社,2008.[4]PeterLinz.形式语言与自动机导论（原书第三版）.北京:机械工业出版社,2005.[5]陈有祺.形式语言与自动机理论.北京:机械工业出版社,2008.第1章 绪论1.1集合的基础知识1.1.1集合及其表示▪集合：一定范围内的、确定的、并且彼此可以区分的对象汇集在一起形成的整体叫做集合(set)，简称为集(set)。▪元素：集合的成员为该集合的元素(element)。N——自然数集Q——有理数集R——实数集Σ——字母集▪集合描述形式：列举法{1
6、,3,5,…}、命题法{x
7、3x2+8x+4=0}。▪基数（势）
8、A
9、。▪集合的分类：空集Φ、有限（穷）集、无穷集、可数集、不可数集。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，且$x∈B，但xÏA，则称A是B的真子集(propersubset)，记作AÌB76▪集合相等如果集合A，B含有的元素完全相同，则称集合A与集合B
10、相等(equivalence)，记作A=B。对任意集合A、B、C：⑴A=BiffAÍB且BÍA。⑵如果AÍB，则
11、A
12、≤
13、B
14、。⑶如果AÌB，则
15、A
16、≤
17、B
18、。⑷如果A是有穷集，且AÌB，则
19、A
20、<
21、B
22、。⑸如果AÍB，则对"x∈A，有x∈B。⑹如果AÌB，则对"x∈A，有x∈B并且$x∈B，但xÏA。⑺如果AÍB且BÍC，则AÍC。⑻如果AÌB且BÌC，或者AÍB且BÌC，或者AÌB且BÍC，则AÌC。⑼如果A=B，则
23、A
24、=
25、B
26、。1.1.3集合的运算▪并(union)A与B的并(union)是一个集合，该集合中的元素要么是
27、A的元素，要么是B的元素，记作A∪B。A∪B={a
28、a∈A或者a∈B}A1∪A2∪…∪An={a
29、$i，1≤i≤n，使得a∈Ai}A1∪A2∪…∪An∪…={a
30、$i，i∈N,使得a∈Ai}▪交(intersection)集合A和B中都有的所有元素放在一起构成的
