1、12023-5-22School of Computer Science,BUPT绪论绪论n 课程信息课程信息n 为什么学习形式语言与自动机为什么学习形式语言与自动机n 形式语言与自动机概述及应用形式语言与自动机概述及应用n 课程内容及要求课程内容及要求22023-5-22School of Computer Science,BUPT 专业基础课专业基础课 -上世纪上世纪 60 60 年代末、年代末、7070年代初，年代初，研究的高峰研究的高峰-之后，向应用领域渗透，之后，向应用领域渗透，研究生课程研究生课程-逐渐普及，逐渐普及，本科阶段的专业基础课本科阶段的专业基础课 专业工作者必须的理论素
2、养专业工作者必须的理论素养 -计算模型计算模型 计算机（不）能够做什么计算机（不）能够做什么 -问题分类问题分类 计算的复杂性，算法分析计算的复杂性，算法分析 -形式系统形式系统 建模工具（状态机建模工具（状态机 ）-抽象描述抽象描述 形式文法、形式表达式形式文法、形式表达式 课课 程程 性性 质质32023-5-22School of Computer Science,BUPT相 关 课 程先修课程先修课程 -离散数学离散数学（数理逻辑，集合论）（数理逻辑，集合论）-计算机导论与程序设计、数据结构计算机导论与程序设计、数据结构 后续课程后续课程 -编译原理编译原理 其它相关课程其它相关课程
3、模式识别、算法分析模式识别、算法分析 42023-5-22School of Computer Science,BUPT为什么学习形式语言与自动机n形式语言与自动机是计算机科学的基础理论形式语言与自动机是计算机科学的基础理论之一，是计算机学科的专业基础课。之一，是计算机学科的专业基础课。n在人工智能、电信领域等有广泛的应用。在人工智能、电信领域等有广泛的应用。n通过一些定理的证明和应用，对大家进行思通过一些定理的证明和应用，对大家进行思维训练，从而为今后学习通信软件，协议工维训练，从而为今后学习通信软件，协议工程，编译技术，人工智能等内容提供理论基程，编译技术，人工智能等内容提供理论基础。础。
4、形式语言与自动机概述及应用n本门课程将围绕着什么是形式语言、什么是自动机、以及形式语言和自动机的相互关系进行阐述。n核心内容核心内容n有限状态自动机，正规语言，正规表达式有限状态自动机，正规语言，正规表达式n上下文无关文法，上下文无关语言，下推自动机上下文无关文法，上下文无关语言，下推自动机n 图灵机，计算问题分类图灵机，计算问题分类52023-5-22School of Computer Science,BUPT62023-5-22School of Computer Science,BUPT1形式语言n什么是形式语言什么是形式语言n形式语言:形式化描述的字母表上的字符串的集形式化描述的字母
5、表上的字符串的集合。合。n字母表：字符的有限集合。ne.g.：26个英文字母构成的字母表。n字符串：字母表中的字符构成的有限序列。ne.g.hello,afjhkfyu 72023-5-22School of Computer Science,BUPT为什么用形式语言为什么用形式语言n自然语言自然语言：人们平时说话时所使用的一种语：人们平时说话时所使用的一种语言，不同的国家和民族有着不同的语言。言，不同的国家和民族有着不同的语言。n形式语言形式语言n通过人们公认的符号，表达方式所描述的通过人们公认的符号，表达方式所描述的一种语言，是一种通用语言，没有国籍之一种语言，是一种通用语言，没有国籍之分
6、。分。n形式语言是某个字母表上的字符串的集合，形式语言是某个字母表上的字符串的集合，有一定的描述范围。有一定的描述范围。82023-5-22School of Computer Science,BUPTn例例1：汉语：汉语：用数用数字、符号等形式化的东西来描述语言字、符号等形式化的东西来描述语言n我吃饭我吃饭 语法正确语法正确n我饭吃我饭吃 语法错误语法错误n饭吃我饭吃我 语法正确，语义错误语法正确，语义错误92023-5-22School of Computer Science,BUPTn例2：T为PASCAL语言所用的全部符号的集合。n正确的PASCAL程序就是T上的语言。n例3：在字母表
7、T=a上，L=a 2n+1|n=0 n表示任意一对aa(包括0对)后跟一个a的字符串。（即含有奇数个a的字符串。）102023-5-22School of Computer Science,BUPTn形式语言的最初起因：语言学家（Chomsky）想用一套形式化方法来描述语言。n形式语言在自然语言研究中起步，在计算机科学中得到广泛应用。n最初的应用：编译 让计算机按照语法规则将高级语言方便地翻译成机器语言。112023-5-22School of Computer Science,BUPTn现在：已广泛应用在人工智能、图象处理、通信协议、通信软件等多个领域n在计算机理论科学方面：是可计算理论（算
8、法在有限步骤内求得解、算法复杂性、停机问题、）、定理自动证明、程序转换（程序自动生成）、模式识别等的基础。122023-5-22School of Computer Science,BUPT 2.自动机自动机n什么是自动机？具有离散输入输出的数学模型。n大量通信软件的基本工作机制都是有限状态自动机。自动机理论在通信领域中的应用极为广泛。132023-5-22School of Computer Science,BUPTn自动机接受一定的输入，执行一定的动作，产生一定的结果。使用状态迁移描述整个工作过程。n状态状态：一个标识，能区分自动机在不同时刻的状况。有限状态系统具有任意有限数目的内部“状态
9、”n自动机的本质自动机的本质：根据状态、输入和规则决定下一个状态状态状态 输入（激励）输入（激励）规则规则 状态迁移状态迁移142023-5-22School of Computer Science,BUPT为什么叫自动机？为什么叫自动机？n可能的状态、运行的规则都是事先确定的。一旦开始运行，就按照事先确定的规则工作，因此叫“自动机”。n有限自动机可以认为是由一个带有读头的有限控制器和一条写有字符的输入带组成。152023-5-22School of Computer Science,BUPTn例1：打电话(自动机在通信领域的应用)。在一次呼叫中，从建立连接到通话完毕，要经历摘机，拨号，应答，
10、进行通话等过程，可以分别用五个状态来表示。q0q0q1q1q2q2q3q3q4q4摘机摘机收到拨号音收到拨号音拨号拨号收应答信号收应答信号挂机挂机收齐号码收齐号码q0:q0:空闲状态空闲状态q1:q1:等待拨号状态等待拨号状态q2:q2:可以拨号状态可以拨号状态q3:q3:等待应答状态等待应答状态q4:q4:通话状态通话状态162023-5-22School of Computer Science,BUPTn例2：串口通信 两台微机通过串口通信,需在两台机器间建立好连接后，才可以传递数据，可以使用有限状态自动机，描述串口通信的状态。传输数据收到应答断开连接连接请求q0q1q2172023-5-
11、22School of Computer Science,BUPTn根据结构不同，自动机又可分为有限自动机，下推自动机，图灵机等。n下推自动机可以看作是由一条输入带，一个有限控制器和一个下推栈组成。n基本图灵机由一个具有读写头的有限控制器和一条无限带组成。n使用自动机，可以形式化的描述现实世界中的一些问题。182023-5-22School of Computer Science,BUPT3形式语言与自动机的关系形式语言与自动机的关系n形式语言和自动机是密切相关的。形式语言 字符串自动机 字符串的识别系统n根据复杂程度可将形式语言分类，根据自动机的接受能力、处理能力的不同也将自动机分类。二者之
12、间具有较好的对应关系。192023-5-22School of Computer Science,BUPT202023-5-22School of Computer Science,BUPT语言与有限自动机（Finite Automata）设设 =0,1 ，L=w w 中至少有一个中至少有一个0 ，如如 0011,10,110111 L,而而11,1111 L。下图是一个可接受该语言的有限状态自动机下图是一个可接受该语言的有限状态自动机 12Start0,101212023-5-22School of Computer Science,BUPT小结n文法是定义语言的一个数学模型，而自动机可看作是语言的识别系统。n通过对一些定理的证明，说明对于一个文法产生的语言，可以构造相应自动机接受该语言：一个自动机接受的语言，可以构造对应的文法产生该语言。一定类型的自动机和某种类型的文法具有等价性。222023-5-22School of Computer Science,BUPT课程内容及要求n课程内容：书上二、三、四、五章。n要求：通过本课学习，要求同学们掌握形式化描述方法，建立起形式语言与自动机的概念，并能在实际中加以应用。n通过对定理的证明，对同学们进行思维训练，并掌握一定的证明方法。
