week1-Introduction.

1CollegeofComputerScience&Technology,BUPTFormalLanguagesandAutomata课程名称形式语言与自动机教师姓名王柏（计算机学院通信软件工程中心）电话62283774Office教三楼616信箱[e-mail]2CollegeofComputerScience&Technology,BUPT绪论课程信息为什么学习形式语言与自动机形式语言与自动机概述及应用课程内容及要求3CollegeofComputerScience&Technology,BUPT专业基础课上世纪60年代末、70年代初，研究的高峰之后，向应用领域渗透，研究生课程近几年，本科阶段的专业基础课专业工作者必须的理论素养计算模型计算机（不）能够做什么问题分类计算的复杂性，算法分析形式系统建模工具（状态机）抽象描述形式文法、形式表达式课程性质4CollegeofComputerScience&Technology,BUPT相关课程先修课程《离散数学》（《数理逻辑》，《集合论》）计算机导论与程序设计、数据结构后续课程《编译原理》其它相关课程《模式识别》、《算法分析》5CollegeofComputerScience&Technology,BUPT教材：形式语言与自动机王柏杨娟编著北京邮电大学出版社2003.16CollegeofComputerScience&Technology,BUPT经典参考书书名IntroductiontoAutomataTheory,Languages,andComputation（SecondEdition）作者JohnE.Hopcroft（Cornell）RajeevMotwani（Stanford）JeffereyD.Ullman（Stanford）出版社AddisonWesley（2001）清华大学出版社（影印版）FirstEdition中译本《自动机理论、语言和计算导引》徐美瑞等译科学出版社，1990John.E.Hopcroft,theTuringAwardwinnerin1986.7CollegeofComputerScience&Technology,BUPT其它参考书《计算理论导引》美M.Sipser张立昂等译机工社2000《形式语言及其句法分析》美A.V.阿霍等科学出版社1987《形式语言与自动机》陈有祺编机工社，2008《形式语言与自动机》蒋宗礼编著清华大学出版社，20038CollegeofComputerScience&Technology,BUPT为什么学习形式语言与自动机形式语言与自动机是计算机科学的基础理论之一，是计算机学科的专业基础课。在人工智能、电信领域等有广泛的应用。通过一些定理的证明和应用，对大家进行思维训练，从而为今后学习通信软件，协议工程，编译技术，人工智能等内容提供理论基础。9CollegeofComputerScience&Technology,BUPT对客观世界的科学研究：目的在于把抽象数学的形式化体系发展成为与现实生活相似的理论模型，从而提供一种通用结构来描述、理解和解决问题。计算机科学：是关于计算知识的有系统的整体。10CollegeofComputerScience&Technology,BUPT计算机科学的两个主要部分：构成计算基础的一些基本概念和模型；设计计算系统(软件和硬件)的工程技术（设计理论的应用）本课程着重介绍第一部分（涉及到一些第二部分的应用），通过形式化技术对大家进行思维训练，为今后的学习打好理论基础。4种基本的专业能力计算思维能力算法的设计与分析能力程序设计和实现能力计算机软硬件系统的认知、分析、设计与应用能力计算思维能力逻辑思维能力和抽象思维能力构造模型对问题进行形式化描述理解和处理形式模型112020/1/10122020/1/10CollegeofComputerScience&Technology,BUPT2020/1/1013能力培养学生的形式化描述和抽象思维能力。使学生了解和初步掌握“问题、形式化描述、自动化（计算机化）”这一最典型的计算机问题求解思路。14CollegeofComputerScience&Technology,BUPT形式语言与自动机概述及应用本门课程将围绕着什么是形式语言、什么是自动机、以及形式语言和自动机的相互关系进行阐述。核心内容有限状态自动机，正规语言，正规表达式上下文无关文法，上下文无关语言，下推自动机图灵机，计算问题分类15CollegeofComputerScience&Technology,BUPT1．形式语言什么是形式语言形式语言:形式化描述的字母表上的字符串的集合。字母表：字符的有限集合。e.g.：26个英文字母构成的字母表。字符串：字母表中的字符构成的有限序列。e.g.hello,afjhkfyu16CollegeofComputerScience&Technology,BUPT为什么用形式语言自然语言：人们平时说话时所使用的一种语言，不同的国家和民族有着不同的语言。形式语言通过人们公认的符号，表达方式所描述的一种语言，是一种通用语言，没有国籍之分。形式语言是某个字母表上的字符串的集合，有一定的描述范围。17CollegeofComputerScience&Technology,BUPT例1：汉语：主谓宾――用数字、符号等形式化的东西来描述语言我吃饭――语法正确我饭吃――语法错误饭吃我――语法正确，语义错误18CollegeofComputerScience&Technology,BUPT例2：T为PASCAL语言所用的全部符号的集合。正确的PASCAL程序就是T上的语言。例3：在字母表T={a}上，L={a2n+1|n=0}表示任意一对aa(包括0对)后跟一个a的字符串。（即含有奇数个a的字符串。）19CollegeofComputerScience&Technology,BUPT形式语言的最初起因：语言学家（Chomsky）想用一套形式化方法来描述语言。形式语言在自然语言研究中起步，在计算机科学中得到广泛应用。最初的应用：编译――让计算机按照语法规则将高级语言方便地翻译成机器语言。20CollegeofComputerScience&Technology,BUPT现在：已广泛应用在人工智能、图象处理、通信协议、通信软件等多个领域在计算机理论科学方面：是可计算理论（算法―在有限步骤内求得解、算法复杂性、停机问题、）、定理自动证明、程序转换（程序自动生成）、模式识别等的基础。21CollegeofComputerScience&Technology,BUPT高级认知活动:对联软件比尔.盖茨：人类计算的未来是让计算机能够看、听、学，能用自然语言与人类交流形式化非常重要唐诗宋词三百首：41850首，8万句，近35万字微软对联软件：微软亚洲研究院自然语言计算组研发的计算机自动对联系统。利用从唐诗宋词大数据中学习到的概率模型，当用户给定上联，能自动提供若干下联；当用户确定一副对联，能生成若干四字横批。网址：图灵测试(1)问：请给我写出有关“第四号桥”主题的十四行诗。答：不要问我这道题，我从来不会写诗。问：34957加70764等于多少？答：（停30秒后）105721问：你会下国际象棋吗？答：是的。问：我在我的K1处有棋子K；你仅在K6处有棋子K，在R1处有棋子R。现在轮到你走，你应该下那步棋？答：（停15秒钟后）棋子R走到R8处，将军！23CollegeofComputerScience&Technology,BUPT图灵测试(2)问：你会下国际象棋吗？答：是的。问：你会下国际象棋吗？答：是的。问：请再次回答，你会下国际象棋吗？答：是的。24CollegeofComputerScience&Technology,BUPT图灵测试(3)问：你会下国际象棋吗？答：是的。问：你会下国际象棋吗？答：是的，我不是已经说过了吗？问：请再次回答，你会下国际象棋吗？答：你烦不烦，干嘛老提同样的问题。25CollegeofComputerScience&Technology,BUPT在线图灵测试网址Elbot一个猜角色机器人（ACharacter-GuessingGame）自动机什么是自动机？具有离散输入输出的数学模型。大量通信软件的基本工作机制都是有限状态自动机。自动机理论在通信领域中的应用极为广泛。27CollegeofComputerScience&Technology,BUPT自动机接受一定的输入，执行一定的动作，产生一定的结果。使用状态迁移描述整个工作过程。状态：一个标识，能区分自动机在不同时刻的状况。有限状态系统具有任意有限数目的内部“状态”自动机的本质：根据状态、输入和规则决定下一个状态状态＋输入（激励）＋规则―状态迁移28CollegeofComputerScience&Technology,BUPT为什么叫自动机？可能的状态、运行的规则都是事先确定的。一旦开始运行，就按照事先确定的规则工作，因此叫“自动机”。有限自动机可以认为是由一个带有读头的有限控制器和一条写有字符的输入带组成。29CollegeofComputerScience&Technology,BUPT例1：打电话(自动机在通信领域的应用)。在一次呼叫中，从建立连接到通话完毕，要经历摘机，拨号，应答，进行通话等过程，可以分别用四个状态来表示。q0q1q2q3q4摘机收到拨号音拨号收应答信号挂机q0:空闲状态q1:等待拨号状态q2:可以拨号状态q3:等待应答状态q4:通话状态30CollegeofComputerScience&Technology,BUPT例2：串口通信两台微机通过串口通信,需在两台机器间建立好连接后，才可以传递数据，可以使用有限状态自动机，描述串口通信的状态。传输数据收到应答断开连接连接请求q0q1q231CollegeofComputerScience&Technology,BUPT根据结构不同，自动机又可分为有限自动机，下推自动机，图灵机等。下推自动机可以看作是由一条输入带，一个有限控制器和一个下推栈组成。基本图灵机由一个具有读写头的有限控制器和一条无限带组成。使用自动机，可以形式化的描述现实世界中的一些问题。32CollegeofComputerScience&Technology,BUPT3．形式语言与自动机的关系形式语言和自动机是密切相关的。形式语言――字符串自动机――字符串的识别系统根据复杂程度可将形式语言分类，根据自动机的接受能力、处理能力的不同也将自动机分类。二者之间具有较好的对应关系。33CollegeofComputerScience&Technology,BUPT34CollegeofComputerScience&Technology,BUPT语言与有限自动机（FiniteAutomata）设=0,1，L=ωω中至少有一个0，如0011,10,110111L,而11,,1111L。下图是一个可接受该语言的有限状态自动机12Start0,10135CollegeofComputerScience&Technology,BUPT小结文法是定义语言的一个数学模型，而自动机可看作是语言的识别系统。通过对一些定理的证明，说明对于一个文法产生的语言，可以构造相