有限自动机理论01章基础知识.ppt

* * * * * * * * * * 就是从普遍性的理论知识出发，去认识个别的、特殊的现象的一种逻辑推理方法。演绎的基本形式是三段论式 . 一般到特殊. * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * B? A * * A ? B * * A ∩ B=0 * * ?和集合A本身都是集合A的子集。 任何集合A的幂集2A的元素都是集合。 * * 笛卡儿是著名的法国哲学家、数学家、物理学家，天文学家、、化学家和生理学家。 解析几何学奠基人之一。 欧洲近代哲学的奠基人之一，黑格尔称他为“现代哲学之父”。 笛卡儿堪称17世纪及其后的欧洲哲学界和科学界最有影响的巨匠之一，被誉为“近代科学的始祖”。 1596年3月31日生于土伦，1650年2月11日卒于斯德哥尔摩。 * * * * * * * 2的m*n方 m*n 0 * * * * [a]=[x] 若 aRx * * * * * * * * * * Chomsky于1959年，将他本人的形式语言的研究成果和Kleene的自动机的研究成果结合起来，不仅确定了文法和自动机分别从产生和识别角度定义语言，而且证明了文法与自动机的等价性。此时，形式语言与自动机理论才真正诞生。并被置于数学的光芒之下。 形式语言与自动机理论出现后，迅速在计算机科学技术领域得到了应用。使用巴科斯-诺尔范式（BNF--Backus-Naur Form）成功地对高级程序设计语言ALGOL-60的词法和语法规则进行了形式化的描述（实际上，巴科斯-诺尔范式就是上下文无关文法的产生式另一种表示方式）。这一成功，使得形式语言与自动机理论得到了进一步的发展。 尤其是上下文无关文法，被作为计算机程序设计语言语法的最佳近似描述得到了较为深入的研究。后来，人们又将上下文无关文法应用到了模式匹配和模型化处理等方面，而这些内容都是算法描述和分析、计算复杂性理论和可计算性理论的研究基础。 形式语言理论的研究对象与以前的所有语言研究不同，不止自然语言，而是人类一切语言：既有自然语言，也有人工语言，包括计算机编程的高级语言。乔姆斯基的形式语言理论得到了多重验证，于是才为语言学界和计算机科学界所折服，“引发了语言学中伽利略式的科学革命的开端。” 乔姆斯基的形式语言理论得到过计算机科学的三种验证。 验证一：乔氏4型文法与4种语言自动机一一对应。 验证二：计算机所使用的各种高级语言，如ALGOL、FORTRAN、PASCAL、C、LISP等，都遵循一种程序语言文法描述的范式，即巴科斯—诺尔范式。计算机科学家发现，巴科斯—诺尔范式等价于乔姆斯基的2型文法，即与上下文无关文法。而乔姆斯基的3型文法——正则文法，在研究文字的计算机模式识别时，也被有效应用。于是，乔氏的4种类型文法被计算机科学界称作乔姆斯基分类。 验证三：乔姆斯基用形式语言理论的思想证明了计算机科学的一个重大理论问题：计算机程序语言是否有歧义性是不可判定的。 20世纪中期，程序语言ALGOL60问世不久，人们发现它有歧义性。当计算机科学家绞尽脑汁寻找办法来判断一种程序语言是否有歧义性时，乔姆斯基用形式语言理论的思想证明，一个任意的上下文无关文法是否有歧义性是不可判定的，因此，属于上下文无关文法的程序语言是否有歧义性也是不可判定的。乔姆斯基的论证令计算机科学界折服。 实际上，形式语言与自动机理论除了在计算机科学与技术领域的直接应用外，更在计算机计算机科学与技术领域的人才的计算思维能力的培养中占有极其重要的地位。 计算机科学与技术学科强调4个方面的专业能力：计算思维能力、算法设计与分析能力、程序设计与实现能力、计算机系统的认知、分析、设计和运用能力。这也是计算机科学与其他学科的重要区别。相关的理论是计算机学科的基础。 理论方面的知识是计算机的真正灵魂。 在本科阶段的学习过程中，学生以观察、描述、比较、分类、推断、应用、创造思维等科学思维过程为主，强调自学的能力在培养； 研究生阶段，需要对学生进一步进行抽象思维、逻辑思维、创造思维能力的培养。 建立物理符号系统并对起实施等价变换是计算机学科进行问题描述和求解的重要手段。“可行性”所要求的“形式化”及其“离散特征”使得数学成为重要的工具，而计算模型无论从方法还是从工具等方面，都表现出它在计算机上科学中的重要作用。 计算机科学与技术学科要求学生具有形式化描述和抽象思维能力，要求掌握逻辑思维方法。这种能力就是计算思维能力或计算机思维能力。 计算机学科系统地研究信息描述和变换算法，重要包括信息描述和变换算法的理论、分析、效率、实现和运用。学科的根本问题在于：什么能被（有效地）自动化？学科的重要内容之一是研究计算领域中的一些普遍