形式语言与自动机课件全全书教学教程完整版电子教案最全幻灯片

《形式语言与自动机课件全全书教学教程完整版电子教案最全幻灯片》由会员分享，可在线阅读，更多相关《形式语言与自动机课件全全书教学教程完整版电子教案最全幻灯片（344页珍藏版）》请在装配图网上搜索。

1、12023-3-11 Formal Languages and Automata形式语言与自动机形式语言与自动机22023-3-11 绪论绪论n 课程信息课程信息n 为什么学习形式语言与自动机为什么学习形式语言与自动机n 形式语言与自动机概述及应用形式语言与自动机概述及应用n 课程内容及要求课程内容及要求32023-3-11 专业基础课专业基础课 -上世纪上世纪 60 60 年代末、年代末、7070年代初，年代初，研究的高峰研究的高峰-之后，向应用领域渗透，之后，向应用领域渗透，研究生课程研究生课程-逐渐普及，逐渐普及，本科阶段的专业基础课本科阶段的专业基础课 专业工作者必须的理论素养专业工作

2、者必须的理论素养 -计算模型计算模型 计算机（不）能够做什么计算机（不）能够做什么 -问题分类问题分类 计算的复杂性，算法分析计算的复杂性，算法分析 -形式系统形式系统 建模工具（状态机建模工具（状态机 ）-抽象描述抽象描述 形式文法、形式表达式形式文法、形式表达式 课课 程程 性性 质质42023-3-11 相 关 课 程先修课程先修课程 -离散数学离散数学（数理逻辑，集合论）（数理逻辑，集合论）-计算机导论与程序设计、数据结构计算机导论与程序设计、数据结构 后续课程后续课程 -编译原理编译原理 其它相关课程其它相关课程 模式识别、算法分析模式识别、算法分析 52023-3-11 为什么学习

3、形式语言与自动机n形式语言与自动机是计算机科学的基础理论形式语言与自动机是计算机科学的基础理论之一，是计算机学科的专业基础课。之一，是计算机学科的专业基础课。n在人工智能、电信领域等有广泛的应用。在人工智能、电信领域等有广泛的应用。n通过一些定理的证明和应用，对大家进行思通过一些定理的证明和应用，对大家进行思维训练，从而为今后学习通信软件，协议工维训练，从而为今后学习通信软件，协议工程，编译技术，人工智能等内容提供理论基程，编译技术，人工智能等内容提供理论基础。础。形式语言与自动机概述及应用n本门课程将围绕着什么是形式语言、什么是自动机、以及形式语言和自动机的相互关系进行阐述。n核心内容核心内

4、容n有限状态自动机，正规语言，正规表达式有限状态自动机，正规语言，正规表达式n上下文无关文法，上下文无关语言，下推自动机上下文无关文法，上下文无关语言，下推自动机n 图灵机，计算问题分类图灵机，计算问题分类62023-3-11 72023-3-11 1形式语言n什么是形式语言什么是形式语言n形式语言:形式化描述的字母表上的字符串的集形式化描述的字母表上的字符串的集合。合。n字母表：字符的有限集合。ne.g.：26个英文字母构成的字母表。n字符串：字母表中的字符构成的有限序列。ne.g.hello,afjhkfyu 82023-3-11 为什么用形式语言为什么用形式语言n自然语言自然语言：人们平

5、时说话时所使用的一种语：人们平时说话时所使用的一种语言，不同的国家和民族有着不同的语言。言，不同的国家和民族有着不同的语言。n形式语言形式语言n通过人们公认的符号，表达方式所描述的通过人们公认的符号，表达方式所描述的一种语言，是一种通用语言，没有国籍之一种语言，是一种通用语言，没有国籍之分。分。n形式语言是某个字母表上的字符串的集合，形式语言是某个字母表上的字符串的集合，有一定的描述范围。有一定的描述范围。92023-3-11 n例例1：汉语：汉语：用数用数字、符号等形式化的东西来描述语言字、符号等形式化的东西来描述语言n我吃饭我吃饭 语法正确语法正确n我饭吃我饭吃 语法错误语法错误n饭吃我饭

6、吃我 语法正确，语义错误语法正确，语义错误102023-3-11 n例2：T为PASCAL语言所用的全部符号的集合。n正确的PASCAL程序就是T上的语言。n例3：在字母表T=a上，L=a 2n+1|n=0 n表示任意一对aa(包括0对)后跟一个a的字符串。（即含有奇数个a的字符串。）112023-3-11 n形式语言的最初起因：语言学家（Chomsky）想用一套形式化方法来描述语言。n形式语言在自然语言研究中起步，在计算机科学中得到广泛应用。n最初的应用：编译 让计算机按照语法规则将高级语言方便地翻译成机器语言。122023-3-11 n现在：已广泛应用在人工智能、图象处理、通信协议、通信软

7、件等多个领域n在计算机理论科学方面：是可计算理论（算法在有限步骤内求得解、算法复杂性、停机问题、）、定理自动证明、程序转换（程序自动生成）、模式识别等的基础。132023-3-11 2.自动机自动机n什么是自动机？具有离散输入输出的数学模型。n大量通信软件的基本工作机制都是有限状态自动机。自动机理论在通信领域中的应用极为广泛。142023-3-11 n自动机接受一定的输入，执行一定的动作，产生一定的结果。使用状态迁移描述整个工作过程。n状态状态：一个标识，能区分自动机在不同时刻的状况。有限状态系统具有任意有限数目的内部“状态”n自动机的本质自动机的本质：根据状态、输入和规则决定下一个状态状态状

8、态 输入（激励）输入（激励）规则规则 状态迁移状态迁移152023-3-11 为什么叫自动机？为什么叫自动机？n可能的状态、运行的规则都是事先确定的。一旦开始运行，就按照事先确定的规则工作，因此叫“自动机”。n有限自动机可以认为是由一个带有读头的有限控制器和一条写有字符的输入带组成。162023-3-11 n例1：打电话(自动机在通信领域的应用)。在一次呼叫中，从建立连接到通话完毕，要经历摘机，拨号，应答，进行通话等过程，可以分别用五个状态来表示。q0q0q1q1q2q2q3q3q4q4摘机摘机收到拨号音收到拨号音拨号拨号收应答信号收应答信号挂机挂机收齐号码收齐号码q0:q0:空闲状态空闲状态

9、q1:q1:等待拨号状态等待拨号状态q2:q2:可以拨号状态可以拨号状态q3:q3:等待应答状态等待应答状态q4:q4:通话状态通话状态172023-3-11 n例2：串口通信 两台微机通过串口通信,需在两台机器间建立好连接后，才可以传递数据，可以使用有限状态自动机，描述串口通信的状态。传输数据收到应答断开连接连接请求q0q1q2182023-3-11 n根据结构不同，自动机又可分为有限自动机，下推自动机，图灵机等。n下推自动机可以看作是由一条输入带，一个有限控制器和一个下推栈组成。n基本图灵机由一个具有读写头的有限控制器和一条无限带组成。n使用自动机，可以形式化的描述现实世界中的一些问题。1

10、92023-3-11 3形式语言与自动机的关系形式语言与自动机的关系n形式语言和自动机是密切相关的。形式语言 字符串自动机 字符串的识别系统n根据复杂程度可将形式语言分类，根据自动机的接受能力、处理能力的不同也将自动机分类。二者之间具有较好的对应关系。202023-3-11 212023-3-11 语言与有限自动机（Finite Automata）设设 =0,1 ，L=w w 中至少有一个中至少有一个0 ，如如 0011,10,110111 L,而而11,1111 L。下图是一个可接受该语言的有限状态自动机下图是一个可接受该语言的有限状态自动机 12Start0,101222023-3-11

11、小结n文法是定义语言的一个数学模型，而自动机可看作是语言的识别系统。n通过对一些定理的证明，说明对于一个文法产生的语言，可以构造相应自动机接受该语言：一个自动机接受的语言，可以构造对应的文法产生该语言。一定类型的自动机和某种类型的文法具有等价性。232023-3-11 课程内容及要求n课程内容：书上二、三、四、五章。n要求：通过本课学习，要求同学们掌握形式化描述方法，建立起形式语言与自动机的概念，并能在实际中加以应用。n通过对定理的证明，对同学们进行思维训练，并掌握一定的证明方法。第二章第二章 语言及文法语言及文法n主要内容主要内容：n定义形式语言的术语定义形式语言的术语n给出文法的定义和文法

12、的分类给出文法的定义和文法的分类n要求掌握：要求掌握：n语言和文法的形式定义语言和文法的形式定义nCHOMSKY文法体系的分类。文法体系的分类。242023-3-11 第一节第一节 语言的定义与运算语言的定义与运算一、一、语言的一些术语：语言的一些术语：n 字母表：字母表：字符的有限集合，记为字符的有限集合，记为T。n字符串：字符串：由字母表由字母表T中的字符构成的序中的字符构成的序列称字母表列称字母表T上的字符串（句子）。上的字符串（句子）。n 常记为常记为u,v,w,x,y,z；n 常用常用a,b,c,d 标识单个字符。标识单个字符。252023-3-11 262023-3-11 字字 母

13、母 表表（Alphabet）概念概念 形式符号的集合形式符号的集合 记号记号 常用常用 T、表示表示 举例举例-英文字母表英文字母表 a,b,z,A,B,Z -英文标点符号表英文标点符号表 ,;:.?!“”()-汉字表汉字表 ,自自,动动,机机,-化学元素表化学元素表 H,He,Li,-T=a,n,y,272023-3-11 字字 符符 串串（string）概念概念 字母表字母表 T 上的一个上的一个字符串字符串（简称（简称串串），或称为），或称为 字字（word），），为为 T 中字符构成的一个有限序列。中字符构成的一个有限序列。空串空串（empty string）,用用 表示，不包含任何字

14、符。表示，不包含任何字符。举例举例 设设 T=a,b ，则则 ,a,ba,bbaba 等都是串等都是串 字符串字符串 w 的的长度长度，记为，记为 w ，是包含在是包含在 w 中字符的中字符的个数。个数。举例举例 =0，bbaba =5 ai 表示含有表示含有i个个a的字符串的字符串 282023-3-11 连接（连接（concatenation）设设 x,y为串为串,且且 x a1a2 am,y b1b2 bn,则则 x 与与 y 的连接的连接 x y a1a2 am b1b2 bn 连接运算的性质连接运算的性质 -(x y)z x（y z）-x x x-x y x+y 关关 于于 字字 符

15、符 串串 的的 运运 算算292023-3-11 其它其它 如如 取头字符取头字符，取尾部取尾部，子串匹配子串匹配 等等n 设设1,2,3是字母表是字母表T上的字符串，称上的字符串，称1是字符是字符串串12的前缀，的前缀，2是字符串是字符串12的后缀，且的后缀，且2是是字符串字符串123的子串。的子串。n 空串是任何字符串的前缀，后缀及子串。空串是任何字符串的前缀，后缀及子串。n 例例：abc的前缀的前缀 a ab abc.后缀后缀 c bc abc.子串子串 a b c ab bc abc ,即一个字符串可以看作是多个字符串的连接。即一个字符串可以看作是多个字符串的连接。关关 于于 字字 符

16、符 串串 的的 运运 算算302023-3-11 n 字符串字符串的逆用的逆用 表示。表示。是字符是字符串串的倒置。的倒置。=b1b2bn =bnbn-1b2b1n 空串空串的逆还是的逆还是312023-3-11 字字 母母 表表 的的 幂幂 运运 算算 幂运算幂运算 设设 T 为字母表，为字母表，n 为任意自然数，为任意自然数，定义（定义（1）T0=（2）设）设 x Tn-1，a T，则则a x Tn （3）Tn 中的元素只能由（中的元素只能由（1）和）和（2）生成）生成 闭包闭包 T*=T0 T1 T2 闭包闭包 T+=T1 T2 T3 T*=T+，T+=T*-322023-3-11 闭包

17、的物理意义闭包的物理意义 T的星号闭包的星号闭包T*：字母表T上的所有字符串和空串的集合。T的正闭包的正闭包T+：字母表T上的所有字符串构成的集合。T*=T+举例举例 设设 T=0，1 ，则则 T0=，T1=0，1 ，T2=00，01，10，11 ，T*=，0，1，00，01，10，11，T+=0，1，00，01，10，11，332023-3-11 语 言（Languages）概念概念 设设 T 为字母表，则任何集合为字母表，则任何集合 L T*是是字母字母表表T上的上的一个语言（一个语言（language）举例举例 -英文单词集英文单词集 ,English,words,-C 语言程序集语言程

18、序集 字母表？字母表？-汉语成语集汉语成语集 ,马到成功马到成功,-化学分子式集化学分子式集 ,H2O,NaCl,-any,342023-3-11 语 言（Languages）举例举例：设：设T=a，b 则则 L1 =anbn|n1 L3=bk|k 是质数是质数 L2 =只有一个空句子的语言只有一个空句子的语言 L4=空语言空语言 均为字母表均为字母表T上的语言。上的语言。由语言的定义知语言是集合，对于集合的运算可由语言的定义知语言是集合，对于集合的运算可应用于对于语言的计算。如并，交，补，差。应用于对于语言的计算。如并，交，补，差。352023-3-11 语言的基本运算 语言的积：语言的积：

19、两个语言L1 和L2的积L1 L2是由L1和L2中的字符串连接所构成的字符串的集合。即L1中所有字符串分别与L2中的字符串连接得到的集合。设T=a,b，L1和 L2是T上的语言。L1=ab,ba L2=aa,bb则 L1 L2=abaa,abbb,baaa,babb L2 L1=aaab,aaba,bbab,bbban L1 L2 L2 L1 语言的积不可交换。语言的积不可交换。362023-3-11 语言的基本运算 语言的幂：语言的幂：语言的幂可归纳定义如下语言的幂可归纳定义如下:L0=Ln=L Ln-1=Ln-1 L n 1上例中，上例中，L12=abab,abba,baab,baba L

20、22=aaaa,aabb,bbaa,bbbb 第二节 文法n定义：所谓文法是用来定义语言的一个数学模型：所谓文法是用来定义语言的一个数学模型n表示语言的方法：n若语言若语言L是有限集合，可用是有限集合，可用列举法n若若L是无限集合（集合中的每个元素有限长度），是无限集合（集合中的每个元素有限长度），用其他方法。用其他方法。n方法一：文法产生系统，由定义的文法规则产方法一：文法产生系统，由定义的文法规则产生出语言的每个句子生出语言的每个句子n方法二：机器识别系统：当一个字符串能被一方法二：机器识别系统：当一个字符串能被一个语言的识别系统接受，则这个字符串是该语个语言的识别系统接受，则这个字符串是

21、该语言的一个句子，否则不属于该语言。言的一个句子，否则不属于该语言。372023-3-11 元语言元语言n定义定义：描述语言的语言描述语言的语言例如：各种各样的程序设计语言例如：各种各样的程序设计语言n当人们要解释或讨论程序设计语言本身时，又需要当人们要解释或讨论程序设计语言本身时，又需要一种语言，被讨论的语言叫做对象语言，即某种程一种语言，被讨论的语言叫做对象语言，即某种程序设计语言，讨论对象语言的语言称为元语言序设计语言，讨论对象语言的语言称为元语言。382023-3-11 BNF（巴科斯范式）巴科斯范式）BNF范式通常被作为讨论某种程序设计语言语法的元语言n:=0|1|2|9 :=“定义

22、为”n:=A|B|C|Z|a|b|z :=|.n通过上述定义可知，所有以字母开头的，由字母和数字组成的字符串都是标识符。nBNF定义了一种语言，其中标识符如上定义。nBNF描述它所定义的语言，为元语言。392023-3-11 n例如：汉语语法中定义了句子的结构由主语、谓语、宾语组成。这里主谓宾只是描述了句子的结构，并不是句子。而按照这种结构组成的建立在汉字上的字符串就是句子。如他是学生。n文法是一种元语言，一种方法，根据文法产文法是一种元语言，一种方法，根据文法产生出语言的句子。生出语言的句子。402023-3-11 三、Chomsky文法体系n例如：BNF:=:=:=:=a|b|z|A|B|

23、Z :=0|1|9将:=改为表示可被代替用I,L,D分别表示标识符、字母、数字;412023-3-11 则上述表达式可以表示为则上述表达式可以表示为 IL IIL IID La|b|.|z D0|1|.9这就是一个文法的生成式集合。这就是一个文法的生成式集合。422023-3-11 nChomsky文法体系中，任何一种文法必须包含有两个不同的有限符号的集合，即非终结符集合N和终结符集合T。一个形式规则的有限集合P（生成式集合），一个起始符S。nP中的生成式是用来产生语言句子的规则，而句子则是仅由终结符组成的字符串。这些字符串必须从一个起始符S开始，不断使用P中的生成式而导出来。n可见文法的核心

24、是生成式的集合，它决定了语言中句子的产生。432023-3-11 文法的形式定义n文法G是一个四元组G=(N，T，P，S)，其中N 非终结符的有限集合T 终结符的有限集合 NT=P 形式为的生成式的有限集合。且(NT)*N+(NT)*,(NT)*S 起始符 且S N。442023-3-11 n将上例用文法表示G=(N，T，P，S)N=I,L,DT=a,b,c,z,0,1,9P=I,La,D0,D9S=I n文法是语言的产生系统，研究怎样构造文法能产生出符合要求的句子。452023-3-11 四推导与句型1、直接推导设G=（N,T,P,S）是文法，若A是P中的生成式，和是（NT）*中的字符串，则

25、有A=称A直接推导出，或说是A的直接推导。462023-3-11 2、推导序列n设G=(N,T,P,S)是文法，、0、1n、都是（NT）*中的字符串，且=0、=n，其中i直接推导出i+1（0in）,则称序列0=1=2=n是长度为n的推导序列，而=0是长度为0的推导序列。n对推导出记为，若推导序列长度大于0，则记为 。n推导序列的每一步，都产生一个字符串，这些字符串一般称为句型。472023-3-11 3、句型和句子n句型字符串字符串是文法是文法G的句型，当且仅当的句型，当且仅当S ，且且（NT）*。n 句子是是G的句子，当且仅当的句子，当且仅当S,且且T*。（是由终结符组成的字符串）是由终结符

26、组成的字符串）例：例：I=L=a I=IL=LL=zL=zbn句型包含句子482023-3-11 4文法产生的语言由文法由文法G产生的语言记为产生的语言记为L(G)。L(G)=|T*且且S 或：或：L(G)中的一个字符串，必是由终结符中的一个字符串，必是由终结符组成的，并且是从起始符组成的，并且是从起始符S推导出来的。推导出来的。492023-3-11 第三节 Chomsky文法体系分类n文法文法 G=(N,T,P,S)；P:其中其中（NT）*N+（NT）*（NT）*属于属于Chomsky文法体系文法体系n该体系对生成式的形式做了一些规定，分该体系对生成式的形式做了一些规定，分为四类，即为四类

27、，即0型、型、1型、型、2型、型、3型文法型文法n0型文法：无限制文法型文法：无限制文法对应的语言：递归可枚举语言，与图灵机等价。502023-3-11 1型文法n也称上下文有关文法（也称上下文有关文法（CSG：Context-sensitive Grammar)生成式的形式为生成式的形式为，其中其中|，（NT）+，（NT）*N+（NT）*n对应的语言：上下文有关语言（对应的语言：上下文有关语言（CSL：Context-sensitive Language)n若不考虑若不考虑，与线性有界自动机（与线性有界自动机（LBA,Linear Bounded Automaton）等价。等价。512023

28、-3-11 2型文法n也称上下文无关文法（也称上下文无关文法（CFG：Context-free Grammar)A,AN,且且（NT）*n对应的语言：上下文无关语言对应的语言：上下文无关语言（CFL：Context-free Language)。n对 应 的 自 动 机：下 推 自 动 机（对 应 的 自 动 机：下 推 自 动 机（P D A：Pushdown Automaton)。522023-3-11 3型文法也称正则文法也称正则文法n右线性文法（右线性文法（Right-linear Grammar）：）：AB 或或 AA、BN,T*。n左线性文法（左线性文法（Left-linear G

29、rammar）：）：AB或或 AA、BN,T*。n对应的语言：正则语言对应的语言：正则语言n对 应 的 自 动 机：有 限 自 动 机（对 应 的 自 动 机：有 限 自 动 机（F i n i t e Automaton）。）。532023-3-11 例例1：G=(A,B,C,a,b,d,P,A)P:AAB，ABCAAB，Ad，Ba，Cb 是是1型文法。型文法。A=dA=AB=dB=daA=AB=ABB=dBB=daB=daaA=AB=CAAB=bAAB=bdAB=bdCAAB=bdbAAB=bdbdAB=bdbddB=bdbdda542023-3-11 例例2：G=(A,B,C,a,b,c

30、,P,A)P:Aabc AaBbc BbbB BcCbcc bCCb aCaaB aCaa 是是1型文法。型文法。其定义的其定义的 L=anbncn|n1n A=abcn A=aBbc=abBc=abCbcc=aCbbcc=aabbcc =aaBbbcc552023-3-11 例例3：G=(S,B,C,a,b,P,A)P:SaC,SbB,BaS,BbBB,Ba,CbS,CaCC,Cb 是是2型文法型文法 n S=aC=ab nS=aC=aaCCnS=aC=abS=abaC=ababS=ababaC=abababnS=bB=bbBB=bbaSB=bbaaCB=bbaabB=bbaaba56202

31、3-3-11 例例4：G=(A,B,C,a,b,c,P,A)P:ABa；Ac；BCb；Ccn左线性文法左线性文法n L=c,cba 正则语言正则语言n注意：已知语言求文法，文法不是唯一的，即可以注意：已知语言求文法，文法不是唯一的，即可以有不同的表达方法有不同的表达方法。572023-3-11 四类文法之间的关系n只是对生成式形式加以限制只是对生成式形式加以限制n0型型 无限制无限制n1型型 不允许不允许A形式形式n2型型n3型型 属于属于2型型n不含不含A的的2型、型、3型属于型属于1型，型，1型、型、2型、型、3型均属于型均属于0型。型。582023-3-11 第三章第三章 有限自动机与右

32、线性文法有限自动机与右线性文法本章主要内容本章主要内容n确定有限自动机确定有限自动机n非确定有限自动机非确定有限自动机n确定与非确定有限自动机的等价性确定与非确定有限自动机的等价性n右线性文法和有限自动机的等价性右线性文法和有限自动机的等价性n右线性文法的性质右线性文法的性质(泵浦定理泵浦定理)n使用归纳法进行证明的方法使用归纳法进行证明的方法592023-3-11 第一节第一节 有限自动机有限自动机一、有限状态系统的概念一、有限状态系统的概念n状态状态:状态是可以将事物状态是可以将事物区分区分开的一种标识。开的一种标识。n具有离散状态的系统：如数字电路具有离散状态的系统：如数字电路(0,1)

33、，十十字路口的红绿灯。离散状态系统的状态数是字路口的红绿灯。离散状态系统的状态数是有限的。有限的。n具有连续状态的系统：比如水库的水位，室具有连续状态的系统：比如水库的水位，室内温度等可以连续变化，即有无穷个状态。内温度等可以连续变化，即有无穷个状态。n有限状态系统必然是离散状态系统（而且状有限状态系统必然是离散状态系统（而且状态数有限），因为只有有限个状态。态数有限），因为只有有限个状态。602023-3-11 n实例实例 一个人带着一头狼，一头羊，以及一棵一个人带着一头狼，一头羊，以及一棵青菜，处于河的左岸。有一条小船青菜，处于河的左岸。有一条小船,每次只能每次只能携带人和其余的三者之一。

34、人和他的伴随品携带人和其余的三者之一。人和他的伴随品都希望渡到河的右岸，而每摆渡一次，人仅都希望渡到河的右岸，而每摆渡一次，人仅能带其中之一。然而如果人留下狼和羊不论能带其中之一。然而如果人留下狼和羊不论在左岸还是在右岸，狼肯定会吃掉羊。类似在左岸还是在右岸，狼肯定会吃掉羊。类似地，如果单独留下羊和菜，羊也肯定会吃掉地，如果单独留下羊和菜，羊也肯定会吃掉菜。如何才能既渡过河而羊和菜又不被吃掉菜。如何才能既渡过河而羊和菜又不被吃掉呢呢?612023-3-11 622023-3-11 MGWC（处于左岸的子集（处于左岸的子集处于右岸的子集处于右岸的子集）将过河问题模型化：将过河问题模型化：人人(M

35、)狼狼(W)羊羊(G)菜菜(C)二、有限自动机的概念二、有限自动机的概念有限自动机的概念有限自动机的概念n具有具有离散离散 输入输入 输出输出系统的系统的一种一种数学模型数学模型(可以没有输出，比较特殊的也可以没有输可以没有输出，比较特殊的也可以没有输入入).n有限有限的状态的状态n状态状态+输入输入状态转移状态转移n每次转换的后继状态都唯一每次转换的后继状态都唯一 DFAn每次转换的后继状态不唯一每次转换的后继状态不唯一 NFA632023-3-11 FA的模型的模型 FA可以理解成一个控制器，它读一条输可以理解成一个控制器，它读一条输入带上的字符。入带上的字符。642023-3-11 10

36、1101有限有限控制器控制器(1)控制器包括有限状态；控制器包括有限状态；(2)从左到右依次读取字符；从左到右依次读取字符；(3)状态状态+激励激励 状态迁移状态迁移(根据当前所处状态和输入字符根据当前所处状态和输入字符进行状态转移进行状态转移)652023-3-11 有限状态集有限状态集 有限输入符号集有限输入符号集 转移函数转移函数 一个开始状态一个开始状态 一个终态集合一个终态集合有限自动机的五要素有限自动机的五要素q0q1q2q3Start01101100三、三、DFA的形式定义的形式定义定义:DFA是一个五元组 M=(Q,T,q0,F)nQ:有限的状态集合有限的状态集合nT:有限的输

37、入字母表有限的输入字母表n:转换函数转换函数(状态转移集合状态转移集合):QT Qnq0:初始状态，初始状态，q0 QnF:终止状态集终止状态集,F Q662023-3-11 转转 移移 图图 表表 示示 的的 DFA672023-3-11 Q=q0,q1,q2,q3 T=0,1 (q0,0)=q2,(q0,1)=q1 (q1,0)=q3,(q1,1)=q0 (q2,0)=q0,(q2,1)=q3 (q3,0)=q1,(q3,1)=q2 q0 F=q0,q3 q0q1q2q3Start01101100682023-3-11 转转 移移 表表 表表 示示 的的 DFA q0q1q2 q301q2

38、q1q3q0q0q3q1q2 Q=q0,q1,q2,q3 T=0,1 (q0,0)=q2,(q0,1)=q1 (q1,0)=q3,(q1,1)=q0 (q2,0)=q0,(q2,1)=q3 (q3,0)=q1,(q3,1)=q2 q0 F=q0,q3 四、四、扩展转移函数适合于输入字符串扩展转移函数适合于输入字符串函数：函数：接收一个字符串的状态转移函数。接收一个字符串的状态转移函数。:Q T*Q 对任何对任何q Q，定义：定义：1.(q,)=q 2.若若是一个字符串是一个字符串,a是一个字符是一个字符定义定义:(q,a)=(q,),a)692023-3-11 扩展转移函数适合于输入字符串扩展

39、转移函数适合于输入字符串702023-3-11 q0q1q2 q301q2q1q3q0q0q3q1q2 举例举例 (q0,)=q0 (q0,0)=(q0,0)=q2 (q0,00)=(q2,0)=q0 (q0,001)=(q0,1)=q1 (q0,0010)=(q1,0)=q3q0q1q2q3Start01101100DFA接受的语言接受的语言n被被DFA接收的字符串接收的字符串:输入结束后使输入结束后使DFA的状态到达终的状态到达终止状态。否则该字符串不能被止状态。否则该字符串不能被D FA接收接收.nDFA接收的语言接收的语言:被被DFA接收的字符串的集合接收的字符串的集合.L(M)=w

40、(q0,w)F n例：例：T=0，1712023-3-11 12Start0110接收含有奇数个接收含有奇数个0的任意串的任意串五、格局五、格局n为描述有限自动机的工作过程，对于它在某为描述有限自动机的工作过程，对于它在某一时刻的工作状态，可用两个信息表明：当一时刻的工作状态，可用两个信息表明：当前状态前状态q，待输入字符串待输入字符串w。两者构成一个瞬两者构成一个瞬时描述，用（时描述，用（q,w）表示，称为格局。表示，称为格局。n初始格局：（初始格局：（q0,w)n终止格局：终止格局：(q,),q F722023-3-11 n如图，接受如图，接受001010的格局的格局（q0,001010）

41、(q2,01010)(q0,1010)(q1,010)(q3,10)(q2,0)(q0,)n格局数量是无限的。格局数量是无限的。n有限状态自动机是无记忆的。有限状态自动机是无记忆的。例如接受例如接受0010101111和接受和接受01011111时，都可以进入格时，都可以进入格局局(q0,1111)。732023-3-11 格局示例格局示例q0q1q2q3Start01101100n如果对某个如果对某个q F,有有(q0,w)(q,),则称输入字符串则称输入字符串w是可被确定的有限自动机接受的。是可被确定的有限自动机接受的。742023-3-11 设计有限自动机设计有限自动机n自动机的设计是一

42、个创造过程，没有简单的算法或过程。自动机的设计是一个创造过程，没有简单的算法或过程。n技巧：假设自己是机器，思考如何去实现机器的任务技巧：假设自己是机器，思考如何去实现机器的任务。n为判断到目前为止所看到的字符串是否满足某个语言，须估为判断到目前为止所看到的字符串是否满足某个语言，须估算出读一个字符串时需要记住哪些关键的东西。算出读一个字符串时需要记住哪些关键的东西。例：例：构造自动机，识别所有由奇数个构造自动机，识别所有由奇数个a和奇数个和奇数个b组成的字符串。组成的字符串。关键：不需要记住所看到的整个字符关键：不需要记住所看到的整个字符串串，只需记住至此所看到，只需记住至此所看到的的a、b

43、个数是偶数还是奇数。个数是偶数还是奇数。752023-3-11 q偶a偶bq奇a偶bq偶a奇bq奇a奇bStartbaabaabb第二节第二节不确定的有限自动机不确定的有限自动机(NFA)修改修改DFA的模型，使之在某个状态，的模型，使之在某个状态，对应一个输入，对应一个输入，可以有多个转移，可以有多个转移，到达不到达不 同的状态，同的状态，则称为不确定的有限则称为不确定的有限自动机。自动机。例：例：762023-3-11 Startpr0,10q1(1)Startp0,11qr0,1(2)一、不确定有限自动机的形式定义一、不确定有限自动机的形式定义nNFA是一个五元组，是一个五元组，M=(Q

44、,T,q0,F)。其中其中是是QT-2Q的函数，其余与的函数，其余与DFA相同。相同。n如果接收一个字符串后如果接收一个字符串后NFA进入一个状态集，进入一个状态集，而此集合中包含而此集合中包含一个以上一个以上F中的状态，中的状态，则则称称NFA接收该字符串。接收该字符串。772023-3-11 782023-3-11 Startpr0,10q1(1)Startp0,11qr0,1(2)pq r0 q q q,r 1pq r0 p r r 1 p,q 转移图和转移表表示的转移图和转移表表示的NFA格局示例格局示例n如图所示，用格局序列描述自动机的工作过程，如图所示，用格局序列描述自动机的工作过

45、程，当输入字符串是当输入字符串是011011时，则有时，则有792023-3-11 Startp0,11qr0,1(,011011)|(,11011)|(,1011)|(,011)|(,11)|(,1)|(,)(,1011)|(,011)(,1)|(,)pppppqrqrpp-(,)q二二、NFA的状态转移函数的状态转移函数 与与 DFA 唯一不同之处唯一不同之处 :Q 2Q同样，同样，可扩展为可扩展为 (:Q T*2Q)1.(q,)=q 含义：不允许无输入的状态变化。2.(q,a)=p|存在存在r(q,)p(r,a)n含义含义:(q,a)对应的状态集合是对应的状态集合是(q,)对应的每个状对

46、应的每个状态态下再下再接收字符接收字符a以后可能到达的状态集合的并集以后可能到达的状态集合的并集.即即若若 (q,)=r 1,r 2,r k,则则 (q,a)=(r i,a)其中其中 T*,a T，r i Q802023-3-11 812023-3-11 举例举例 (p,)=p (p,0)=q (p,01)=q,r (p,010)=q (p,0100)=q (p,01001)=q,r pq r0 q q q,r 1扩展转移函数适合于输入字符串扩展转移函数适合于输入字符串Startpr0,10q1822023-3-11 NFA 接受的语言接受的语言 设一个设一个 NFA A=(Q,T,q0,F)

47、定义定义 A 的语言的语言:L(A)=w (q0,w)F 第三节第三节 NFA与与DFA的等价性的等价性nDFA是是NFA的特例，所以的特例，所以NFA必然能接收必然能接收DFA能接收能接收的语言。的语言。因此因此证明等价性只要能够证明一个证明等价性只要能够证明一个NFA所所能接收的语言必能被另一个能接收的语言必能被另一个DFA所接收所接收。1.定理：设一个定理：设一个NFA接受语言接受语言L，那么必然存在一个，那么必然存在一个DFA接受接受L。2.证明证明:n策略：对于任意一个策略：对于任意一个NFA，构造一个接收它所能接，构造一个接收它所能接收语言的收语言的DFA，这个这个DFA的状态对应

48、的状态对应了了NFA的状态的状态集合。集合。832023-3-11 842023-3-11 从从 NFA 构造等价的构造等价的 DFA (子集构造法子集构造法)设设 L 是某个是某个 NFA MN=(QN,T,N,q0,FN)的语言的语言,则存在一个则存在一个 DFA MD,满足满足 L(MD)=L(MN)=L.证明证明:定义定义 M D=(QD,T,D,q0,FD),其中其中 QD=S S QN =2 Q 对对 S QD 和和 a T,D(S,a)=N(q,a)，FD=S S QN S FN 需要证明需要证明:对任何对任何w T*,D(q0 ,w)=N(q0,w).归纳于归纳于|w|可可证上

49、述命题证上述命题.q S852023-3-11 pq r0 q q q,r 10 q 1 p q r p,q p,r q,r p,q,r q q,r q q,r q q q,r q q,r Startp0,10q1q,r1010 子集构造法举例子集构造法举例862023-3-11 pq r0 p r r 1 p,q 01 p p,q,r p p,q p p,q p,q p,r p,q,r p,r p,r p,q,r Startp1p,q10100p,q,rp,r01子集构造法举例子集构造法举例Startp0,11qr0,1872023-3-11 证明证明:从从 NFA 构造等价的构造等价的 D

50、FA 设设 MN=(QN,T,N,q0,FN)是一个是一个 NFA,通过子集构造法通过子集构造法 得到相应的得到相应的DFA MD=(QD,T,D,q0,FD),则则 对任何对任何w T*,D(q0 ,w)=N(q0,w).证明证明:归纳于归纳于|w|1 设设|w|=0,即即 w=.由定义知由定义知 D(q0 ,)=N(q0,)=q0 .2 设设|w|=n+1,并并 w=xa,a T.注意到注意到|x|=n.假设假设 D(q0 ,x)=N(q0,x)=p1,p2,pk .则则 D(q0 ,w)=D(D(q0 ,x),a)=D(p1,p2,pk,a)=N(pi,a).=N(q0,w)i=1k88

51、2023-3-11 实践中实践中,通过子集构造法得到的通过子集构造法得到的 DFA 的状态数目的状态数目与与原原NFA 的状态数目的状态数目大体大体相当相当.在较坏的情况下在较坏的情况下,上述上述 DFA 的状态数目接近于所有的状态数目接近于所有子集的数目子集的数目.举例举例 由如下由如下 NFA 构造的构造的 DFA 的状态数目至少为的状态数目至少为2n子集构造法得到的状态数子集构造法得到的状态数Start0,110,10,10,1.q0q1q2qn第四节第四节有有 转换的转换的NFAn一、定义一、定义概念：当输入空串概念：当输入空串(无输入无输入)时，也能引时，也能引起状态的转移。起状态的

52、转移。例：892023-3-11 q2q00q22q00q1q0输入输入“002”时的转移格局：时的转移格局：q0q1q2012902023-3-11 -NFA 的形式定义的形式定义 一个一个 -NFA 是一个五元组是一个五元组 A=(Q,T,q0,F).有限状态集有限状态集 有限输入符号集有限输入符号集 转移函数转移函数 一个开始状态一个开始状态 一个终态集合一个终态集合q0 Q F Q 与与 NFA 的不同之处的不同之处 :Q (T )2Q912023-3-11 -NFA 如何接受输入符号串如何接受输入符号串Start0,1,.,9.0,1,.,90,1,.,90,1,.,9.q1q0q2

53、q3q5 ,+,q4 该该 -NFA 可以接受的字符串如：可以接受的字符串如：3.14 +.314 314.922023-3-11 二、二、-闭包（闭包（closure）概念概念 状态状态 q 的的 -闭包闭包，记为，记为 -CLOSURE 或或ECLOSE，定义为从，定义为从 q 经所有的经所有的 路径可以到达路径可以到达的状态（包括的状态（包括q自身），自身），如：如：q0q1q2012 -CLOSURE(q0)=q0,q1,q2 -CLOSURE(q1)=q1,q2 -CLOSURE(q2)=q2 状态子集状态子集I I 的的-闭包：闭包：-CLOSURE(I)-CLOSURE(q)qI

54、例：例：-CLOSURE(q1，q2)-CLOSURE(q1)-CLOSURE(q2)q1，q2nIa Ia 概念：概念：对于状态子集对于状态子集I Q，任意任意aT，定义定义Ia如下：如下：Ia=-Closure(P)其中其中P=（I，a）.即即P是从是从I中的状态经过一条标中的状态经过一条标a的边可以到达的状态集合的边可以到达的状态集合 932023-3-11 942023-3-11 例：例：I Iq0q0，q1q1，求求I I1 1I I1 1 -CLOSURE-CLOSURE（I I，1 1）-CLOSURE-CLOSURE（q0q0，q1q1，1 1）-CLOSURE-CLOSURE

55、（q1 q1）q1q1，q2q2q0q1q2012952023-3-11 扩展转移函数适合于输入字符串扩展转移函数适合于输入字符串 设一个设一个 -NFA,:Q T 2Q 扩充定义扩充定义 :Q T*2Q 对任何对任何q Q，定义：定义：1 (q,)=ECLOSE(q)2(q，a)-CLOSURE(P)其中其中P p|存在存在r(q，)p(r，a)注意：注意：此时此时(q，a)(q，a)，因为因为(q，a)表示由表示由q出发，只沿着标出发，只沿着标a 的路径所能到达的状态，的路径所能到达的状态，而而(q，a)表示由表示由q出发，沿着标出发，沿着标a(包括包括转换在内转换在内)的路径所能到的路径

56、所能到达的状态达的状态.962023-3-11-NFA中，中，与与 函数的不同函数的不同 举例举例 计算计算 (q0,a)(q0，)-CLOSURE(q0)q0，q2(q0，a)-CLOSURE(q0，)，a)-CLOSURE(q0，q2，a)-CLOSURE(q0，a)(q2，a)-CLOSURE(q1q3)q1，q2 q3q1，q2，q3 同理：同理：(q0，aa)q3q q0 0q q2 2q q3 3q q1 1abab-CLOSURE(q0)q0，q2-CLOSURE(q1)q1，q2-CLOSURE(q2)q2-CLOSURE(q3)q3972023-3-11 三、三、-NFA 的

57、的 语语 言言 设一个设一个 -NFA M=(Q,T,q0,F)定义定义 M 的语言：的语言：L(M)=|(q0,)F 即即 满足满足(q0，)含有含有F的一个状态的一个状态 四、有四、有 转换的转换的NFA与无与无 转换的转换的NFA的等价的等价1.-NFANFA具有具有转移的转移的NFA是不具是不具转移的转移的NFA的一的一般情况，所以只要证明下面的定理即可：般情况，所以只要证明下面的定理即可：定理：如果定理：如果L被一个具有被一个具有 转移的转移的NFA接收，接收，那么那么L可被一个不具可被一个不具 转移的转移的NFA 接收。接收。证明证明思路：构造一个不具思路：构造一个不具 转移的转移

58、的NFA，证明证明其其接收具有接收具有 转移的转移的NFA所接受的语言。所接受的语言。982023-3-11 992023-3-11 从从 -NFA 构造等价的构造等价的 无无 NFA 设设 M=(Q,T,q0,F)是一个是一个 -NFA，可构造一个无，可构造一个无 的的 NFA M1=(Q,T,1,q0,F1)，对任何对任何 a T,1(q,a)=(q,a)。（注意（注意与与的区别与联系。而的区别与联系。而1和和是相等的。）是相等的。）F1 Fq0 若若-CLOSURE(q0)F F 否则否则1002023-3-11 从从 -NFA 构造等价的构造等价的 无无 NFA 证明证明:采用归纳法证

59、明采用归纳法证明1（q0，）（q0，），），|=1|=1。当当|w|=0,即即 w=时，不一定相等时，不一定相等.1(q0，)q0，而而(q0，)-CLOSURE(q0)因此，从因此，从|1开始证明开始证明 1.当当|=1时，定义相等。时，定义相等。由由1定义定义 1（q0，a）（q0，a）设当设当|=n时，时，1（q0,）=（q0,），），则则当当|a|=n+1时，时，左侧左侧 1（q0,a）1(1（q0，），），a)1(（q0，），），a)由归纳假设由归纳假设1(R，a)设设R（q0，）1(q，a)q R(q，a)q R.由由1定义定义(R，a)(（q0，），），a)R（q0，）(q0，a

60、)右侧右侧再证再证:1（q0，）含含F1的一个状态当且仅当的一个状态当且仅当（q0，）含含F的一的一个状态个状态 （略）（略）1012023-3-11 证明同时展示了一种将证明同时展示了一种将 -NFA转化为转化为NFA的方法的方法.-NFA NFA DFA例：将将 -NFA转换为转换为NFA.（图3.4.1，3.4.3）1022023-3-11 q0q1q2012q0q1q20120,11,20,1,21032023-3-11 举例举例Start0,1,.,9.0,1,.,90,1,.,90,1,.,9.q1q0q2q3q5 ,+,q4Startq0+,-q10,1,.,9q1 q4.q20

61、,1,.,9.0,1,.,9.q2 q3 q50,1,.,9q3 q50,1,.,90,1,.,91042023-3-11 第五节 正则集和正则式正则集：正则集：字母表上一些特殊形式的字符串的集合，字母表上一些特殊形式的字符串的集合，是正则式所表示的集合。是正则式所表示的集合。正则式正则式：用类似代数表达式的方法表示正则语言。：用类似代数表达式的方法表示正则语言。运算运算:作用于语言上的三种代数运算作用于语言上的三种代数运算-联合联合（union）-连接连接（concatenation）-（星）星）闭包闭包（closure）1052023-3-11 正则表达式（正则表达式（regular ex

62、pression）归纳定义归纳定义正则表达式正则表达式如下：如下：基础基础：，a（aT）都是正则式都是正则式(原子正则式原子正则式)，相应的正则集为相应的正则集为，a归纳：归纳：如果如果A和和B是正则式，且分别代表集合是正则式，且分别代表集合L(A)和和L(B)，则则(A+B)，(A.B)，A*也是正则式，分别表示以下正则集：也是正则式，分别表示以下正则集：L(A)L(B)(语言语言A/语言语言B的串的串)L(A).L(B)(两个语言中的串的连接两个语言中的串的连接)L(A)*(语言语言A中的串的多次连接中的串的多次连接)仅通过有限次使用以上两步定义的表达式，才是字母表T上的正则式。这些正则式

63、所表示的字符串集合是T上的正则集。1062023-3-11 正则表达式算符优先级正则表达式算符优先级 算符优先级（算符优先级（precedence）依次为依次为-（closure）-连接连接（concatenation）-（union）定义：若两个正则式表示相同的正则集，则称这两个正则式相等。即 R1R2 L(R1)=L(R2)注1：正则集是T*的子集。注2：L+包含当且仅当L包含。注3：每个正则集至少对应一个正则式（可有无穷多个正则式）1072023-3-11 正则表达式举例正则表达式举例书书p55 例例1 表示如下语言的正则表达式：语言中的每表示如下语言的正则表达式：语言中的每个字符串由个

64、字符串由交替的交替的 0 s 和和 1 s 构成构成-(01)*+(10)*+0(10)*+1(01)*-(+1)(01)*(+0)-(+0)(10)*(+1)1082023-3-11 语言的语言的联合（联合（union）运算运算 两个语言两个语言 L 和和 M 的联合的联合 L M=w w L w M 举例举例 设设 L=001,10,111 ,M=,001,则则 L M=,10,001,111 1092023-3-11 语言的语言的连接（连接（concatenation）运算运算 两个语言两个语言 L 和和 M 的的连接连接 L M=w1w2 w1 L w2 M 有时记有时记 L M 为为

65、 LM 举例举例 设设 L=001,10,111 ,M=,001,则则 LM=001,10,111,001001,10001,111001 1102023-3-11 语言的语言的闭包（闭包（closure）运算运算 语言语言 L 的闭包的闭包 L*=wn w L n 0 ,其中其中wn 为为w 的的 n 次连接次连接 或或 L*=L0 L1 L2 =i 0 Li,其中其中 L0=，L1=L,L2=LL,举例举例 设设 L=0,11 ,则则 L*=,0,11,00,011,110,1111,000,0011,0110,01111,1100,11011,11110,111111,1112023-3

66、-11 正则式的性质正则式的性质交换律（交换律（commutativity）和结合律和结合律（associativeity）(1)(+)+(+)(2)()()(3)+等幂律（等幂律（idempotent law）(4)+分配律（分配律（distributive law）(5)(+)+(6)(+)+1122023-3-11 正则式的性质正则式的性质幺元（幺元（identities）和零元（和零元（annihilators）(7)+(8)(9)与闭包相关的定律与闭包相关的定律(10)(*)*(11)*+*=*=L+=LL*=L*L （L+的定义）的定义）L*=L+1132023-3-11 正则式的性质正则式的性质(11)*+*证明：证明：*2n L(*)L()L(2)L(n)L(+*)L()(L()L(2)L(n)L()L(*)而而 L()L(*)+*1142023-3-11 右线性文法右线性文法与与正则式正则式 右右(左左)线性文法又称为正则文法，右线性文法与线性文法又称为正则文法，右线性文法与正则式可以用来代表同一正则语言。二者具有等效正则式可以用来代表同一正则语言。二者具有等效性。性