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