形式语言与自动机.ppt

《形式语言与自动机.ppt》由会员分享，可在线阅读，更多相关《形式语言与自动机.ppt（48页珍藏版）》请在三一办公上搜索。

1、1,2023/5/27,College of Computer Science&Technology,BUPT,Formal Languages and Automata,课程名称 形式语言与自动机 教师姓名 杨娟（计算机学院 软件工程中心）电话 6228 3779 信箱,2,2023/5/27,College of Computer Science&Technology,BUPT,绪论,课程信息 为什么学习形式语言与自动机 形式语言与自动机概述及应用 课程内容及要求,3,2023/5/27,College of Computer Science&Technology,BUPT,专业基础课 上

2、世纪 60 年代末、70年代初，研究的高峰 之后，向应用领域渗透，研究生课程 近几年，本科阶段的专业基础课 专业工作者必须的理论素养 计算模型 计算机（不）能够做什么 问题分类 计算的复杂性，算法分析 形式系统 建模工具（状态机）抽象描述 形式文法、形式表达式,课 程 性 质,4,2023/5/27,College of Computer Science&Technology,BUPT,相 关 课 程,先修课程 离散数学（数理逻辑，集合论）计算机导论与程序设计、数据结构 后续课程 编译原理 其它相关课程模式识别、算法分析,5,2023/5/27,College of Computer Scie

3、nce&Technology,BUPT,教材：形式语言与自动机 王柏 杨娟 编著 北京邮电大学出版社 2003.1,6,2023/5/27,College of Computer Science&Technology,BUPT,经 典 参 考 书,书名 Introduction to Automata Theory,Languages,and Computation（Second Edition）作者 John E.Hopcroft（Cornell）Rajeev Motwani（Stanford）Jefferey D.Ullman（Stanford）出版社 Addison Wesley（200

4、1）清华大学出版社（影印版）First Edition 中译本自动机理论、语言和计算导引 徐美瑞 等译 科学出版社，1990,John.E.Hopcroft,the Turing Awardwinner in 1986.,7,2023/5/27,College of Computer Science&Technology,BUPT,其它参 考 书,自动机理论及其应用 何成武 科学出版社1990形式语言及其句法分析 美A.V.阿霍 等 科学出版社1987 形式语言 王兵山，吴兵 编 国防工业大学出版社，1988 形式语言与自动机理论 蒋宗礼，姜守旭.清华大学出版社，2003形式语言与自动机 陈有

5、祺 编著 机械工业出版社，2008,8,2023/5/27,College of Computer Science&Technology,BUPT,为什么学习形式语言与自动机,形式语言与自动机是计算机科学的基础理论之一，是计算机学科的专业基础课。在人工智能、电信领域等有广泛的应用。通过一些定理的证明和应用，对大家进行思维训练，从而为今后学习通信软件，协议工程，编译技术，人工智能等内容提供理论基础。,9,2023/5/27,College of Computer Science&Technology,BUPT,对客观世界的科学研究：目的在于把抽象数学的形式化体系发展成为与现实生活相似的理论模型，

6、从而提供一种通用结构来描述、理解和解决问题。计算机科学：是关于计算知识的有系统的整体。,10,2023/5/27,College of Computer Science&Technology,BUPT,计算机科学的两个主要部分：构成计算基础的一些基本概念和模型；设计计算系统(软件和硬件)的工程技术（设计理论的应用）本课程着重介绍第一部分（涉及到一些第二部分的应用），通过形式化技术对大家进行思维训练，为今后的学习打好理论基础。,4种基本的专业能力计算思维能力算法的设计与分析能力程序设计和实现能力计算机软硬件系统的认知、分析、设计与应用能力计算思维能力逻辑思维能力和抽象思维能力构造模型对问题进行形

7、式化描述理解和处理形式模型,11,2023/5/27,12,2023/5/27,College of Computer Science&Technology,BUPT,2023/5/27,13,能力培养学生的形式化描述和抽象思维能力。使学生了解和初步掌握“问题、形式化描述、自动化（计算机化）”这一最典型的计算机问题求解思路。,形式语言与自动机概述及应用,本门课程将围绕着什么是形式语言、什么是自动机、以及形式语言和自动机的相互关系进行阐述。核心内容有限状态自动机，正规语言，正规表达式上下文无关文法，上下文无关语言，下推自动机 图灵机，计算问题分类,14,2023/5/27,College of

8、Computer Science&Technology,BUPT,15,2023/5/27,College of Computer Science&Technology,BUPT,1形式语言,什么是形式语言形式语言:形式化描述的字母表上的字符串的集合。字母表：字符的有限集合。e.g.：26个英文字母构成的字母表。字符串：字母表中的字符构成的有限序列。e.g.hello,afjhkfyu,16,2023/5/27,College of Computer Science&Technology,BUPT,为什么用形式语言,自然语言：人们平时说话时所使用的一种语言，不同的国家和民族有着不同的语言。形式

9、语言通过人们公认的符号，表达方式所描述的一种语言，是一种通用语言，没有国籍之分。形式语言是某个字母表上的字符串的集合，有一定的描述范围。,17,2023/5/27,College of Computer Science&Technology,BUPT,例1：汉语：用数字、符号等形式化的东西来描述语言我吃饭 语法正确我饭吃 语法错误饭吃我 语法正确，语义错误,18,2023/5/27,College of Computer Science&Technology,BUPT,例2：T为PASCAL语言所用的全部符号的集合。正确的PASCAL程序就是T上的语言。例3：在字母表T=a上，L=a 2n+1

10、|n=0 表示任意一对aa(包括0对)后跟一个a的字符串。（即含有奇数个a的字符串。）,19,2023/5/27,College of Computer Science&Technology,BUPT,形式语言的最初起因：语言学家（Chomsky）想用一套形式化方法来描述语言。形式语言在自然语言研究中起步，在计算机科学中得到广泛应用。最初的应用：编译 让计算机按照语法规则将高级语言方便地翻译成机器语言。,20,2023/5/27,College of Computer Science&Technology,BUPT,现在：已广泛应用在人工智能、图象处理、通信协议、通信软件等多个领域在计算机理论

11、科学方面：是可计算理论（算法在有限步骤内求得解、算法复杂性、停机问题、）、定理自动证明、程序转换（程序自动生成）、模式识别等的基础。,21,2023/5/27,College of Computer Science&Technology,BUPT,比尔.盖茨：人类计算的未来是让计算机能够看、听、学，能用自然语言与人类交流 形式化非常重要例1：微软对联软件网址：例2：图灵测试,22,2023/5/27,College of Computer Science&Technology,BUPT,图灵测试(1),问：请给我写出有关“第四号桥”主题的十四行诗。答：不要问我这道题，我从来不会写诗。问：349

12、57加70764等于多少？答：（停30秒后）105721问：你会下国际象棋吗？答：是的。问：我在我的K1处有棋子K；你仅在K6处有棋子K，在R1处有棋子R。现在轮到你走，你应该下那步棋？答：（停15秒钟后）棋子R走到R8处，将军！,23,2023/5/27,College of Computer Science&Technology,BUPT,图灵测试(2),问：你会下国际象棋吗？答：是的。问：你会下国际象棋吗？答：是的。问：请再次回答，你会下国际象棋吗？答：是的。,24,2023/5/27,College of Computer Science&Technology,BUPT,图灵测试(3)

13、,问：你会下国际象棋吗？答：是的。问：你会下国际象棋吗？答：是的，我不是已经说过了吗？问：请再次回答，你会下国际象棋吗？答：你烦不烦，干嘛老提同样的问题。,25,2023/5/27,College of Computer Science&Technology,BUPT,在线图灵测试网址,Artificial solutionAliceElbot,例3：人机大战2011年2月17日，经过3天比赛，IBM新一代超级电脑系统“沃森”，最终在美国的著名智力游戏节目危险边缘中击败了两位人类选手肯詹宁斯和布拉德鲁特取得冠军，并且赢取了100万美元的奖金。1997年超级计算机“深蓝”力克国际世界冠军卡斯帕罗

14、夫。“沃森”的名字取自于IBM创始人托马斯沃森，它是IBM亲历打造的最新一代电脑超级系统，为了完成一项艰巨挑战，建造一个能够与人类答题能力相匹敌的计算系统。沃森”参加的是智力问答比赛，而不是国际象棋对弈，想当年“深蓝”只要具有足够强大的计算能力就一定能够获胜，但是“沃森”不同，它需要识别非常复杂的人类语言，并要从中分析微妙的含义，讽刺口吻以及各种暗示，理清各种逻辑线索，还要能猜谜语，进行构词断句，并通过一系列数字比对和模拟人类的联想能力得出精准的答案，再反向使用人类的语言进行答题。而且这整个分析解答过程仅凭计算机和软件算法的完成，没有工程师的参与，也没有互联网的支持。而“沃森”的出现会节省我们

15、很多劳动力，比如说有一张报表，上面有很多需要我们去填的东西，你把这张报表给“沃森”看一看它就能得出答案;它在搜索方面也会有比较大的潜力，平时我们搜索可能是输入一个关键词，得出一大堆的答案，然后我们一个一个的去找，但只要把我们需要的东西告诉给“沃森”，“沃森”就会给我们一个准确的答案，这就是它最好的一个地方。,26,2023/5/27,College of Computer Science&Technology,BUPT,27,2023/5/27,College of Computer Science&Technology,BUPT,2.自动机,什么是自动机？具有离散输入输出的数学模型。大量通信

16、软件的基本工作机制都是有限状态自动机。自动机理论在通信领域中的应用极为广泛。,28,2023/5/27,College of Computer Science&Technology,BUPT,自动机接受一定的输入，执行一定的动作，产生一定的结果。使用状态迁移描述整个工作过程。状态：一个标识，能区分自动机在不同时刻的状况。有限状态系统具有任意有限数目的内部“状态”自动机的本质：根据状态、输入和规则决定下一个状态状态 输入（激励）规则 状态迁移,29,2023/5/27,College of Computer Science&Technology,BUPT,为什么叫自动机？,可能的状态、运行的规则

17、都是事先确定的。一旦开始运行，就按照事先确定的规则工作，因此叫“自动机”。有限自动机可以认为是由一个带有读头的有限控制器和一条写有字符的输入带组成。,30,2023/5/27,College of Computer Science&Technology,BUPT,例1：打电话(自动机在通信领域的应用)。在一次呼叫中，从建立连接到通话完毕，要经历摘机，拨号，应答，进行通话等过程，可以分别用五个状态来表示。,31,2023/5/27,College of Computer Science&Technology,BUPT,例2：串口通信 两台微机通过串口通信,需在两台机器间建立好连接后，才可以传递数

18、据，可以使用有限状态自动机，描述串口通信的状态。,32,2023/5/27,College of Computer Science&Technology,BUPT,根据结构不同，自动机又可分为有限自动机，下推自动机，图灵机等。下推自动机可以看作是由一条输入带，一个有限控制器和一个下推栈组成。基本图灵机由一个具有读写头的有限控制器和一条无限带组成。使用自动机，可以形式化的描述现实世界中的一些问题。,33,2023/5/27,College of Computer Science&Technology,BUPT,3形式语言与自动机的关系,形式语言和自动机是密切相关的。形式语言 字符串自动机 字符串

19、的识别系统根据复杂程度可将形式语言分类，根据自动机的接受能力、处理能力的不同也将自动机分类。二者之间具有较好的对应关系。,34,2023/5/27,College of Computer Science&Technology,BUPT,35,2023/5/27,College of Computer Science&Technology,BUPT,语言与有限自动机（Finite Automata）,设=0,1，L=w w 中至少有一个0，如 0011,10,110111 L,而11,1111 L。下图是一个可接受该语言的有限状态自动机,36,2023/5/27,College of Compu

20、ter Science&Technology,BUPT,小结,文法是定义语言的一个数学模型，而自动机可看作是语言的识别系统。通过对一些定理的证明，说明对于一个文法产生的语言，可以构造相应自动机接受该语言：一个自动机接受的语言，可以构造对应的文法产生该语言。一定类型的自动机和某种类型的文法具有等价性。,37,2023/5/27,College of Computer Science&Technology,BUPT,课程内容及要求,课程内容：书上二、三、四、五章。要求：通过本课学习，要求同学们掌握形式化描述方法，建立起形式语言与自动机的概念，并能在实际中加以应用。通过对定理的证明，对同学们进行思维

21、训练，并掌握一定的证明方法。,38,2023/5/27,College of Computer Science&Technology,BUPT,证 明 技 术*,基本证明方法 归纳证明技术,*引自清华大学计算机系软件技术研究所王生原老师课件,39,2023/5/27,College of Computer Science&Technology,BUPT,演 绎 证 明,概念 一个 证明（proof）是命题的序列，其中的每一个命题或者是已知的命题，或者是由前面出现过的命题使用逻辑公理和规则得出.已知的命题集合称为假设（hypothesis）或前提（premise），最后一个命 题称为该前提的结论

22、（conclusion）.,40,2023/5/27,College of Computer Science&Technology,BUPT,“If Then”命题,证明方法把 If 部分作为已知的命题，把 Then 部分作为结论.举例 如果x+y=1，那么x2-y2=x-y.证明:,1 x2-y2=(x+y)(x-y)/数学公理,2(x+y)=1/已知,x2-y2=x-y/由1、2 和算术性质推出,41,2023/5/27,College of Computer Science&Technology,BUPT,“If-And-Only-If”命题,欲证 A if and only if B，

23、可分别证明如下两个命题：1 if A then B，2 if B then A.,42,2023/5/27,College of Computer Science&Technology,BUPT,有关集合的命题,设 R,S 为集合.欲证 R S，可证明如下命题：if xR then xS 欲证 R=S，可分别证明如下两个命题：1 if xR then xS 2 if xS then xR,43,2023/5/27,College of Computer Science&Technology,BUPT,原命题的逆否命题,有时，证明原命题的逆否(contrapositive)命题更加方便.欲证 i

24、f A then B，可证明如下命题：if not B then not A,44,2023/5/27,College of Computer Science&Technology,BUPT,反证法,反证（proof by contradiction）欲证 if H then C，可以把 H 和 not C 都作为已知的命题，把任何一个矛盾(contradiction)命题作为新的结论.,45,2023/5/27,College of Computer Science&Technology,BUPT,举例证明或否证,举例证明存在量化的命题 如命题：存在整数 a，满足 a2=2a.证明:取 a=

25、2.，满足 a2=2a.举反例否定全称量化的命题如命题：所有整数 a，都满足 a2=2a.否证:取 a=1.，不满足 a2=2a.,46,2023/5/27,College of Computer Science&Technology,BUPT,集合的归纳定义 由 3 部分构成：1 基础（basis）/直接定义集合中的元素（至少1个）2 归纳（induction）/从已知元素生成新元素的规则 3 极小性限制/申明集合中的元素只能由 1、2 生成 结构归纳法 对于归纳定义的集合 S，欲证对于任意xS，满足性质P(x).1 基础（basis）/若有直接定义 aS，则证明 P(a)2 归纳（indu

26、ction）/若归纳定义中有规则 if a1,a2,an S then f(a1,a2,an)S，则证明 if P(a1),P(a2),P(an)then P(f(a1,a2,an),归 纳 定 义 与 结 构 归 纳 法,47,2023/5/27,College of Computer Science&Technology,BUPT,归纳定义合法括号串的集合 S 1 基础 空串 S 2 归纳 若 xS，则(x)S；若 x,y S，则 xy S.3 极小性限制 S 中的元素只能由 1、2 生成(或：S是满足1、2的最小集合)命题：合法括号串集合 S 中每个括号串的“(”与“)”数目相等 证明:

27、1 基础 空串 的“(”与“)”数目相等，都为0；2 归纳 设 x,y 的“(”与“)”数目相等，前者为m，后者为n；(x)的“(”与“)”数目都为m+1；xy 的“(”与“)”数目都为m+n.,归纳定义与结构归纳证明（例）,48,2023/5/27,College of Computer Science&Technology,BUPT,自然数 自然数集合N是满足如下条件的最小集合：(1)0 N;(2)若 n N,则n的后继n+1 N 数学归纳法 欲证对任意自然数n，P(n)成立，(1)先证 P(0)成立;(2)再证若 P(n)成立,则P(n+1)成立 另一种形式(1)先证P(0)成立;(2)再证若对任意kn，P(k)成立,则P(n)成立 对任何良序集合，都可以有这两种形式,基于自然数的归纳 一般数学归纳法,