形式语言与自动机.ppt

例2：串口通信 两台微机通过串口通信,需在两台机器间建立好连接后，才可以传递数据，可以使用有限状态自动机，描述串口通信的状态。传输数据收到应答断开连接连接请求q0q1q2根据结构不同，自动机又可分为有限自动机，下推自动机，图灵机等。01使用自动机，可以形式化的描述现实世界中的一些问题。04下推自动机可以看作是由一条输入带，一个有限控制器和一个下推栈组成。02基本图灵机由一个具有读写头的有限控制器和一条无限带组成。03形式语言和自动机是密切相关的。形式语言――字符串自动机――字符串的识别系统根据复杂程度可将形式语言分类，根据自动机的接受能力、处理能力的不同也将自动机分类。二者之间具有较好的对应关系。010302语言与有限自动机（FiniteAutomata）设?=?0,1?，L=?w?w中至少有一个0?，如0011,10,110111?L,而11,?,1111?L。下图是一个可接受该语言的有限状态自动机?logo文法是定义语言的一个数学模型，而自动机可看作是语言的识别系统。通过对一些定理的证明，说明对于一个文法产生的语言，可以构造相应自动机接受该语言：一个自动机接受的语言，可以构造对应的文法产生该语言。一定类型的自动机和某种类型的文法具有等价性。CollegeofComputerScienceTechnology,BUPTCollegeofComputerScienceTechnology,BUPT课程名称形式语言与自动机教师姓名杨娟（计算机学院软件工程中心）电话62283779信箱yangjuan@bupt.edu.cn01课程信息03形式语言与自动机概述及应用02为什么学习形式语言与自动机04课程内容及要求计算模型计算机（不）能够做什么问题分类计算的复杂性，算法分析形式系统建模工具（状态机?）抽象描述形式文法、形式表达式专业工作者必须的理论素养专业基础课上世纪60年代末、70年代初，研究的高峰之后，向应用领域渗透，研究生课程近几年，本科阶段的专业基础课相关课程**CollegeofComputerScienceTechnology,BUPT先修课程《离散数学》（《数理逻辑》，《集合论》）计算机导论与程序设计、数据结构后续课程《编译原理》其它相关课程《模式识别》、《算法分析》?教材：**CollegeofComputerScienceTechnology,BUPT形式语言与自动机01王柏杨娟编著02北京邮电大学出版社2003.103书名IntroductiontoAutomataTheory,Languages,andComputation（SecondEdition）作者JohnE.Hopcroft（Cornell）RajeevMotwani（Stanford）JeffereyD.Ullman（Stanford）出版社AddisonWesley（2001）清华大学出版社（影印版）FirstEdition中译本《自动机理论、语言和计算导引》徐美瑞等译科学出版社，1990John.E.Hopcroft,theTuringAwardwinnerin1986.蒋宗礼，姜守旭.清华大学出版社，2003《形式语言与自动机理论》04王兵山，吴兵编国防工业大学出版社，1988《形式语言》03美A.V.阿霍等科学出版社1987《形式语言及其句法分析》02何成武科学出版社1990《自动机理论及其应用》01陈有祺编著机械工业出版社，2008《形式语言与自动机》05030201形式语言与自动机是计算机科学的基础理论之一，是计算机学科的专业基础课。在人工智能、电信领域等有广泛的应用。通过一些定理的证明和应用，对大家进行思维训练，从而为今后学习通信软件，协议工程，编译技术，人工智能等内容提供理论基础。对客观世界的科学研究：目的在于把抽象