计算理论及有穷自动机.ppt

计算理论导引参考文献1.J.Hopcroft,R.Motwani,J.DUllman.自动机理论、语言和计算导论（第二版），刘田，姜晖，王捍贫译．北京：机械工业出版社，2004．2.蒋宗礼，姜守旭.形式语言与自动机理论（第二版）.北京：清华大学出版社，2007．3.E.Rich.Automata,Computability,andComplexityTheoryandApplications(影印版），北京：清华大学出版社，2009．参考文献4.T.A.Sudkamp,LanguagesandMachines-AnIntroductiontothetheoryofComputerScience(ThirdEdition)（影印版），北京：清华大学出版社，2009．5.M.Sipser,计算理论导引，张里昂，王捍贫，黄雄译，北京：机械工业出版社，2000.6.P.Linz,AnIntroductiontoFormalLanguagesandAutomata(3ed)(影印版),北京：机械工业出版社，2004.第一章导引（Introduction）§1.1计算理论简介本课程集中在计算理论的三个传统的核心领域：§1.1计算理论这个问题可回溯到20世纪30年代，那时数理逻辑学家们首先探讨计算的含义。自那时起，技术进步极大地增强了我们的计算能力，并把这个问题从理论王国带进现实世界。计算的问题是各种各样的，有的容易，有的困难。是什么使某些问题很难计算，又使另一些问题容易计算。§1.1计算理论-复杂性的度量复杂性的度量:耗费的时间,耗费的存储.多项式时间(P),非确定多项式时间(NP),多项式空间(PSPACE),指数时间(EXP),…受到复杂性理论的直接影响的一个应用领域是密码技术，通常情况下，容易计算的问题比难问题更可取，因为求解容易问题代价要小。§1.1计算理论-可计算性理论在20世纪前半叶，数学家们，如哥德尔（G?del）、图灵（Turing）及丘奇（Church），发现一些基本问题是不能用计算机解决的。可计算性理论与复杂性理论是密切相关的。在复杂性理论中，目标是把问题分成容易的和困难的；§1.1计算理论-自动机理论与形式语言1951年到1956年，克林(Kleene)在研究神经细胞中,建立了识别语言的系统——有穷状态自动机。有穷自动机(FA)性质.存储量极小的计算机在文本处理,编译程序及硬件设计中有应用下推自动机(PDA)性质.带一个栈的计算机在程序设计语言和人工智能中有应用图灵机(TM)性质.有无限可改写存储的计算机能解决实际计算机所能解决的一切问题FA和PDA是简化的图灵机一般将以图灵机作为计算的理论模型20世纪50年代，巴科斯范式(BackusNourForm或BackusNormalForm，BNF)实现了对高级语言ALGOL-60的成功描述。这一成功，使得形式语言在20世纪60年代得到了大力的发展。尤其是上下文无关文法被作为计算机程序设计语言的文法的最佳近似描述得到了较为深入的研究。上下文无关文法的模型在程序设计语言和人工智能中有用。自动机理论是学习计算机理论的极好起点。可计算性和复杂性理论需要给计算机下一个精确的定义。自动机理论允许在引入与计算机科学的其他非理论领域有关的概念时使用计算的形式化定义。自动机理论与形式语言在计算机科学与技术学科的人才的计算思维的培养中占有极其重要的地位。§1.5自动机理论的中心概念-字母表定义1.5.1字母表（alphabet）：∑为有限非空集。§1.5自动机理论的中心概念-串§1.5自动机理论的中心概念-字母表的幂☆注1:⑴∑*={x|x是∑中的若干个，包括0个字符，连接而成的一个字符串}。⑵∑+={x|x是∑中的至少一个字符连接而成的字符串}。§1.5自动机理论的中心概念-串的连接串的运算：连接（concatenation）§1.5自动机理论的中心概念-串的前缀与后缀设x，y，z，w，v∈∑*，且x=yz，w=yv(1)?y是x的前缀(prefix)。(2)如果z≠ε，则y是x的真前缀(properprefix)。(3)z是x的后缀(suffix)；(4)如果y≠ε，则z是x的真后缀(propersuffix)。§1.5自动机理论的中心概念-语言