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

《形式语言与自动机课件(全)全书教学教程完整版电子教案最全幻灯片.ppt》由会员分享，可在线阅读，更多相关《形式语言与自动机课件(全)全书教学教程完整版电子教案最全幻灯片.ppt（344页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、-问题分分类 计算的复算的复杂性，算法分析性，算法分析 -形式系形式系统 建模工具（状建模工具（状态机机 ）-抽象描述抽象描述 形式文法、形式表达式形式文法、形式表达式课课程程性性质质42023/3/4 相 关 课 程先修先修课程程 -离散数学离散数学（数理（数理逻辑，集合，集合论）-计算机算机导论与程序与程序设计、数据、数据结构构 后后续课程程 -编译原理原理 其它相关其它相关课程程 模式模式识别、算法分析、算法分析 52023/3/4 为什么学习形式语言与自动机n形式形式语言与自言与自动机是机是计算机科学的基算机科学的基础理理论之一，是之一，是计算机学科的算机学科的专业基基础课。n在人工智

3、能、在人工智能、电信信领域等有广泛的域等有广泛的应用。用。n通通过一一些些定定理理的的证明明和和应用用，对大大家家进行行思思维训练，从从而而为今今后后学学习通通信信软件件，协议工工程程，编译技技术，人人工工智智能能等等内内容容提提供供理理论基基础。形式语言与自动机概述及应用n本门课程将围绕着什么是形式语言、什么是自动机、以及形式语言和自动机的相互关系进行阐述。n核心内容核心内容n有限状态自动机，正规语言，正规表达式有限状态自动机，正规语言，正规表达式n上下文无关文法，上下文无关语言，下推自动机上下文无关文法，上下文无关语言，下推自动机n 图灵机，计算问题分类图灵机，计算问题分类62023/3/

4、4 72023/3/4 1形式语言n什么是形式什么是形式语言言n形式语言:形形式式化化描描述述的的字字母母表表上上的的字字符符串串的的集合。集合。n字母表：字符的有限集合。ne.g.：26个英文字母构成的字母表。n字符串：字母表中的字符构成的有限序列。ne.g.hello,afjhkfyu82023/3/4 为什么用形式语言为什么用形式语言n自自然然语言言：人人们平平时说话时所所使使用用的的一一种种语言，不同的国家和民族有着不同的言，不同的国家和民族有着不同的语言。言。n形式形式语言言n通通过人人们公公认的的符符号号，表表达达方方式式所所描描述述的的一一种种语言言，是是一一种种通通用用语言言，

5、没没有有国国籍籍之之分。分。n形形式式语言言是是某某个个字字母母表表上上的的字字符符串串的的集集合合，有一定的描述范有一定的描述范围。92023/3/4 n例例1：汉语：用用数字、符号等形式化的数字、符号等形式化的东西来描述西来描述语言言n我吃我吃饭语法正确法正确n我我饭吃吃语法法错误n饭吃我吃我语法正确，法正确，语义错误102023/3/4 n例2：T为PASCAL语言所用的全部符号的集合。n正确的PASCAL程序就是T上的语言。n例3：在字母表T=a上，L=a2n+1|n=0n表示任意一对aa(包括0对)后跟一个a的字符串。（即含有奇数个a的字符串。）112023/3/4 n形 式 语 言

6、 的 最 初 起 因：语 言 学 家（Chomsky）想用一套形式化方法来描述语言。n形式语言在自然语言研究中起步，在计算机科学中得到广泛应用。n最初的应用：编译让计算机按照语法规则将高级语言方便地翻译成机器语言。122023/3/4 n现在：已广泛应用在人工智能、图象处理、通信协议、通信软件等多个领域n在计算机理论科学方面：是可计算理论（算法在有限步骤内求得解、算法复杂性、停机问题、）、定理自动证明、程序转换（程序自动生成）、模式识别等的基础。132023/3/4 2.自动机自动机n什么是自动机？具有离散输入输出的数学模型。n大量通信软件的基本工作机制都是有限状态自动机。自动机理论在通信领域

7、中的应用极为广泛。142023/3/4 n自动机接受一定的输入，执行一定的动作，产生一定的结果。使用状态迁移描述整个工作过程。n状状态：一个标识，能区分自动机在不同时刻的状况。有限状态系统具有任意有限数目的内部“状态”n自自动机机的的本本质：根据状态、输入和规则决定下一个状态状状态输入（激励）入（激励）规则状状态迁移迁移152023/3/4 为什么叫自动机？为什么叫自动机？n可能的状态、运行的规则都是事先确定的。一旦开始运行，就按照事先确定的规则工作，因此叫“自动机”。n有限自动机可以认为是由一个带有读头的有限控制器和一条写有字符的输入带组成。162023/3/4 n例1：打电话(自动机在通信

8、领域的应用)。在一次呼叫中，从建立连接到通话完毕，要经历摘机，拨号，应答，进行通话等过程，可以分别用五个状态来表示。q0q0q1q1q2q2q3q3q4q4摘机摘机收到拨号音收到拨号音拨号拨号收应答信号收应答信号挂机挂机收齐号码收齐号码q0:q0:空闲状态空闲状态q1:q1:等待拨号状态等待拨号状态q2:q2:可以拨号状态可以拨号状态q3:q3:等待应答状态等待应答状态q4:q4:通话状态通话状态172023/3/4 n例2：串口通信 两台微机通过串口通信,需在两台机器间建立好连接后，才可以传递数据，可以使用有限状态自动机，描述串口通信的状态。传输数据收到应答断开连接连接请求q0q1q2182

9、023/3/4 n根据结构不同，自动机又可分为有限自动机，下推自动机，图灵机等。n下推自动机可以看作是由一条输入带，一个有限控制器和一个下推栈组成。n基本图灵机由一个具有读写头的有限控制器和一条无限带组成。n使用自动机，可以形式化的描述现实世界中的一些问题。192023/3/4 3形式语言与自动机的关系形式语言与自动机的关系n形式语言和自动机是密切相关的。形式语言字符串自动机字符串的识别系统n根据复杂程度可将形式语言分类，根据自动机的接受能力、处理能力的不同也将自动机分类。二者之间具有较好的对应关系。202023/3/4 212023/3/4 语言与有限自动机（Finite Automata）

10、设=0,1，L=w w中至少有一个中至少有一个0，如如0011,10,110111 L,而而11,1111 L。下下图是一个可接受是一个可接受该语言的有限状言的有限状态自自动机机 222023/3/4 小结n文法是定义语言的一个数学模型，而自动机可看作是语言的识别系统。n通过对一些定理的证明，说明对于一个文法产生的语言，可以构造相应自动机接受该语言：一个自动机接受的语言，可以构造对应的文法产生该语言。一定类型的自动机和某种类型的文法具有等价性。232023/3/4 课程内容及要求n课程内容：书上二、三、四、五章。n要求：通过本课学习，要求同学们掌握形式化描述方法，建立起形式语言与自动机的概念，

11、并能在实际中加以应用。n通过对定理的证明，对同学们进行思维训练，并掌握一定的证明方法。第二章第二章 语言及文法语言及文法n主要内容主要内容：n定定义形式形式语言的言的术语n给出文法的定出文法的定义和文法的分和文法的分类n要求掌握：要求掌握：n语言和文法的形式定言和文法的形式定义nCHOMSKY文法体系的分文法体系的分类。242023/3/4 第一节第一节 语言的定义与运算语言的定义与运算一、一、语言的一些言的一些术语：n字母表：字母表：字符的有限集合，字符的有限集合，记为T。n字符串：字符串：由字母表由字母表T中的字符构成的序中的字符构成的序列称字母表列称字母表T上的字符串（句子）。上的字符串

12、（句子）。n常常记为u,v,w,x,y,z；n常用常用a,b,c,d标识单个字符。个字符。252023/3/4 262023/3/4 字字母母表表（Alphabet）概念概念 形式符号的集合形式符号的集合 记号号常用常用T、表示表示 举例例-英文字母表英文字母表 a,b,z,A,B,Z-英文英文标点符号表点符号表,;:.?!“”()-汉字表字表,自自,动,机机,-化学元素表化学元素表 H,He,Li,-T=a,n,y,272023/3/4 字字符符串串（string）概念概念字母表字母表T上的一个上的一个字符串字符串（简称称串串），或称），或称为 字字（word），），为T中字符构成的一个有限

13、序列。中字符构成的一个有限序列。空串空串（emptystring）,用用 表示，不包含任何字符。表示，不包含任何字符。举例例设T=a,b，则,a,ba,bbaba等都是串等都是串 字符串字符串w的的长度度，记为 w，是包含在是包含在w中字符的中字符的个数。个数。举例例 =0，bbaba=5ai表示含有表示含有i个个a的字符串的字符串 282023/3/4 连接（接（concatenation）设x,y为串串,且且x a1a2am,y b1b2bn,则x与与y的的连接接 xy a1a2amb1b2bn连接运算的性接运算的性质-(xy)z x（yz）-x x x-xy x+y 关关 于于 字字 符

14、符 串串 的的 运运 算算292023/3/4 其它其它如如取取头字符字符，取尾部取尾部，子串匹配子串匹配等等n 设1,2,3是是字字母母表表T上上的的字字符符串串，称称1是是字字符符串串12的的前前缀，2是是字字符符串串12的的后后缀，且且2是是字符串字符串123的子串。的子串。n空串是任何字符串的前空串是任何字符串的前缀，后，后缀及子串。及子串。n例例：abc的前的前缀aababc.后后缀cbcabc.子串子串abcabbcabc,即一个字符串可以看作是多个字符串的即一个字符串可以看作是多个字符串的连接。接。关关 于于 字字 符符 串串 的的 运运 算算302023/3/4 n字符串字符串

15、的逆用的逆用表示。表示。是是字符串字符串的倒置。的倒置。=b1b2bn=bnbn-1b2b1n空串空串的逆的逆还是是312023/3/4 字字 母母 表表 的的 幂 运运 算算幂运算运算设T为字母表，字母表，n为任意自然数，任意自然数，定定义（1）T0=（2）设x Tn-1，a T，则ax Tn（3）Tn中的元素只能由（中的元素只能由（1）和）和（2）生成）生成 闭包包T*=T0 T1 T2 闭包包T+=T1 T2 T3 T*=T+，T+=T*322023/3/4 闭包的物理意包的物理意义T的星号的星号闭包包T*：字母表T上的所有字符串和空串的集合。T的正的正闭包包T+：字母表T上的所有字符串

16、构成的集合。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/4 语 言（Languages）概念概念设设T为字母表，则任何集合为字母表，则任何集合L T*是是字母字母表表T上的上的一个语言（一个语言（language）举例举例-英文单词集英文单词集,English,words,-C语言程序集语言程序集 字母表？字母表？-汉语成语集汉语成语集,马到成功马到成功,-化学分子式集化学分子式集,H2O,NaCl,-any,342023/3/4 语 言（Languages

17、）举例举例：设T=a，b则L1=anbn|n1L3=bk|k是是质数数L2=只有一个空句子的只有一个空句子的语言言L4=空空语言言均均为字母表字母表T上的上的语言。言。由由语言的定言的定义知知语言是集合，言是集合，对于集合的运算可于集合的运算可应用于用于对于于语言的言的计算。如并，交，算。如并，交，补，差。，差。352023/3/4 语言的基本运算语言的积：语言的积：两个语言L1和L2的积L1L2是由L1和L2中的字符串连接所构成的字符串的集合。即L1中所有字符串分别与L2中的字符串连接得到的集合。设T=a,b，L1和L2是T上的语言。L1=ab,baL2=aa,bb则L1L2=abaa,ab

18、bb,baaa,babbL2L1=aaab,aaba,bbab,bbbanL1L2L2L1语言的言的积不可交不可交换。362023/3/4 语言的基本运算语言的幂：语言的幂：语言的言的幂可可归纳定定义如下如下:L0=Ln=LLn-1=Ln-1Ln1上例中，上例中，L12=abab,abba,baab,babaL22=aaaa,aabb,bbaa,bbbb第二节 文法n定义：所：所谓文法是用来定文法是用来定义语言的一个数学模型言的一个数学模型n表示语言的方法：n若若语言言L是有限集合，可用是有限集合，可用列举法n若若L是是无无限限集集合合（集集合合中中的的每每个个元元素素有有限限长度度），用其他

19、方法。用其他方法。n方方法法一一：文文法法产生生系系统，由由定定义的的文文法法规则产生出生出语言的每个句子言的每个句子n方方法法二二：机机器器识别系系统：当当一一个个字字符符串串能能被被一一个个语言言的的识别系系统接接受受，则这个个字字符符串串是是该语言的一个句子，否言的一个句子，否则不属于不属于该语言。言。372023/3/4 元语言元语言n定定义：描述描述语言的言的语言言例如：各种各例如：各种各样的程序的程序设计语言言n当当人人们要要解解释或或讨论程程序序设计语言言本本身身时，又又需需要要一一种种语言言，被被讨论的的语言言叫叫做做对象象语言言，即即某某种种程程序序设计语言，言，讨论对象象语

20、言的言的语言称言称为元元语言言。382023/3/4 BNF（巴科斯范式）巴科斯范式）BNF范式通常被作为讨论某种程序设计语言语法的元语言n:=0|1|2|9:=“定义为”n:=A|B|C|Z|a|b|z:=|.n通过上述定义可知，所有以字母开头的，由字母和数字组成的字符串都是标识符。nBNF定义了一种语言，其中标识符如上定义。nBNF描述它所定义的语言，为元语言。392023/3/4 n例如：汉语语法中定义了句子的结构由主语、谓语、宾语组成。这里主谓宾只是描述了句子的结构，并不是句子。而按照这种结构组成的建立在汉字上的字符串就是句子。如他是学生。n文文法法是是一一种种元元语言言，一一种种方方

21、法法，根根据据文文法法产生出生出语言的句子。言的句子。402023/3/4 三、Chomsky文法体系n例如：BNF:=:=:=:=a|b|z|A|B|Z:=0|1|9将:=改为表示可被代替用I,L,D分别表示标识符、字母、数字;412023/3/4 则上述表达式可以表示上述表达式可以表示为ILIILIIDLa|b|.|zD0|1|.9这就是一个文法的生成式集合。就是一个文法的生成式集合。422023/3/4 nChomsky文法体系中，任何一种文法必须包含有两个不同的有限符号的集合，即非终结符集合N和终结符集合T。一个形式规则的有限集合P（生成式集合），一个起始符S。nP中的生成式是用来产生

22、语言句子的规则，而句子则是仅由终结符组成的字符串。这些字符串必须从一个起始符S开始，不断使用P中的生成式而导出来。n可见文法的核心是生成式的集合，它决定了语言中句子的产生。432023/3/4 文法的形式定义n文法G是一个四元组G=(N，T，P，S)，其中N 非终结符的有限集合T终结符的有限集合NT=P 形式为的生成式的有限集合。且(NT)*N+(NT)*,(NT)*S 起始符且SN。442023/3/4 n将上例用文法表示G=(N，T，P，S)N=I,L,DT=a,b,c,z,0,1,9P=I,La,D0,D9S=In文法是语言的产生系统，研究怎样构造文法能产生出符合要求的句子。452023

23、/3/4 四推导与句型1、直接推导设G=（N,T,P,S）是文法，若A是P中的生成式，和是（NT）*中的字符串，则有A=称A直接推导出，或说是A的直接推导。462023/3/4 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/4 3、句型和句子n句型字符串字符串是文法是文法G的句型，当且的句型，当且仅当当S，

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

25、成成式式的的形形式式做做了了一一些些规定定，分分为四四类，即，即0型、型、1型、型、2型、型、3型文法型文法n0型文法：无限制文法型文法：无限制文法对应的语言：递归可枚举语言，与图灵机等价。502023/3/4 1型文法n也称上下文有关文法（也称上下文有关文法（CSG：Context-sensitiveGrammar)生成式的形式生成式的形式为，其中其中|，（NT）+，（NT）*N+（NT）*n对应的的语言：上下文有关言：上下文有关语言（言（CSL：Context-sensitiveLanguage)n若不考若不考虑，与与线性有界自性有界自动机（机（LBA,LinearBoundedAutom

26、aton）等价。等价。512023/3/4 2型文法n也也称称上上下下文文无无关关文文法法（CFG：Context-freeGrammar)A,AN,且且（NT）*n对应的的语言言：上上下下文文无无关关语言言（CFL：Context-freeLanguage)。n对 应 的的 自自 动 机机：下下 推推 自自 动 机机（PDA：PushdownAutomaton)。522023/3/4 3型文法也称正也称正则文法文法n右右线性文法（性文法（Right-linearGrammar）：）：AB或或AA、BN,T*。n左左线性文法（性文法（Left-linearGrammar）：）：AB或或AA、B

27、N,T*。n对应的的语言：正言：正则语言言n对应的自的自动机：有限自机：有限自动机（机（FiniteAutomaton）。）。532023/3/4 例例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/4 例例2：G=(A,B,C,a,b,c,P,A)P:AabcAaBbcBbbBBcCbccbCCbaCaaBaCaa 是是1型文法。型文法。其定其定

28、义的的L=anbncn|n1nA=abcnA=aBbc=abBc=abCbcc=aCbbcc=aabbcc=aaBbbcc552023/3/4 例例3：G=(S,B,C,a,b,P,A)P:SaC,SbB,BaS,BbBB,Ba,CbS,CaCC,Cb是是2型文法型文法n S=aC=abnS=aC=aaCCnS=aC=abS=abaC=ababS=ababaC=abababnS=bB=bbBB=bbaSB=bbaaCB=bbaabB=bbaaba562023/3/4 例例4：G=(A,B,C,a,b,c,P,A)P:ABa；Ac；BCb；Ccn左左线性文法性文法nL=c,cba正正则语言言n注

29、注意意：已已知知语言言求求文文法法，文文法法不不是是唯唯一一的的，即即可可以以有不同的表达方法有不同的表达方法。572023/3/4 四类文法之间的关系n只是只是对生成式形式加以限制生成式形式加以限制n0型型无限制无限制n1型型不允不允许A形式形式n2型型n3型型属于属于2型型n不不含含A的的2型型、3型型属属于于1型型，1型型、2型、型、3型均属于型均属于0型。型。582023/3/4 第三章第三章有限自动机与右线性文法有限自动机与右线性文法本章主要内容本章主要内容n确定有限自确定有限自动机机n非确定有限自非确定有限自动机机n确定与非确定有限自确定与非确定有限自动机的等价性机的等价性n右右线

30、性文法和有限自性文法和有限自动机的等价性机的等价性n右右线性文法的性性文法的性质(泵浦定理浦定理)n使用使用归纳法法进行行证明的方法明的方法592023/3/4 第一节第一节有限自动机有限自动机一、有限状一、有限状态系系统的概念的概念n状状态:状状态是可以将事物是可以将事物区分区分开的一种开的一种标识。n具有离散状具有离散状态的系的系统：如数字：如数字电路路(0,1)，十字路口的十字路口的红绿灯。离散状灯。离散状态系系统的状的状态数数是有限的。是有限的。n具有具有连续状状态的系的系统：比如水：比如水库的水位，室的水位，室内温度等可以内温度等可以连续变化，即有无化，即有无穷个状个状态。n有限状有

31、限状态系系统必然是离散状必然是离散状态系系统（而且状（而且状态数有限），因数有限），因为只有有限个状只有有限个状态。602023/3/4 n实例例 一一个个人人带着着一一头狼狼，一一头羊羊，以以及及一一棵棵青青菜菜，处于于河河的的左左岸岸。有有一一条条小小船船,每每次次只只能能携携带人人和和其其余余的的三三者者之之一一。人人和和他他的的伴伴随随品品都都希希望望渡渡到到河河的的右右岸岸，而而每每摆渡渡一一次次，人人仅能能带其其中中之之一一。然然而而如如果果人人留留下下狼狼和和羊羊不不论在在左左岸岸还是是在在右右岸岸，狼狼肯肯定定会会吃吃掉掉羊羊。类似似地地，如如果果单独独留留下下羊羊和和菜菜，羊

32、羊也也肯肯定定会会吃吃掉掉菜菜。如如何何才才能能既既渡渡过河河而而羊羊和和菜菜又又不不被被吃吃掉掉呢呢?612023/3/4 622023/3/4 MGWC（处于于左左岸岸的的子子集集处于右岸的子集于右岸的子集）将将过河河问题模型化：模型化：人人(M)狼狼(W)羊羊(G)菜菜(C)二、有限自动机的概念二、有限自动机的概念有限自有限自动机的概念机的概念n具有具有离散离散输输入入输输出出系系统的的一种一种数学模型数学模型(可可以以没没有有输输出出，比比较较特特殊殊的的也也可可以以没没有有输输入入).n有限有限的状的状态态n状状态+输入入状状态转移移n每次每次转换的后的后继状状态都唯一都唯一DFAn

33、每次每次转换的后的后继状状态不唯一不唯一NFA632023/3/4 FA的模型的模型FA可以理解成一个控制器，它可以理解成一个控制器，它读一条一条输入入带上的字符。上的字符。642023/3/4 101101有限有限控制器控制器(1)控制器包括有限状控制器包括有限状态态；(2)从左到右依次从左到右依次读读取字符；取字符；(3)状状态态+激励激励状状态态迁移迁移(根据当前所根据当前所处处状状态态和和输输入字符入字符进进行状行状态转态转移移)652023/3/4 有限状有限状态集集 有限有限输入符号集入符号集 转移函数移函数 一个开始状一个开始状态 一个一个终态集合集合有限自有限自动机的五要素机的

34、五要素q0q1q2q3三、三、DFA的形式定义的形式定义定义:DFA是一个五元组M=(Q,T,q0,F)nQ:有限的状有限的状态集合集合nT:有限的有限的输入字母表入字母表n:转换函数函数(状状态转移集合移集合):QTQnq0:初始状初始状态，q0 QnF:终止状止状态集集,F Q662023/3/4 转转移移图图表表示示的的DFA672023/3/4 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,q3q0q1q2q3682023/

35、3/4 转移移表表表表示示的的DFA q0q1q2 q301q2q1q3q0q0q3q1q2Q=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,)=q2.若若是一个字符串是一个字符串,a是一个字符是一个字符定定义:(q,a)=(q,),a)692023/3/

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

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

38、)(q0,)n格局数量是无限的。格局数量是无限的。n有限状有限状态自自动机是无机是无记忆的。的。例如接受例如接受0010101111和接受和接受01011111时，都可以，都可以进入格入格局局(q0,1111)。732023/3/4 格局示例格局示例q0q1q2q3n如果如果对某个某个q F,有有(q0,w)(q,),则称称输入字符串入字符串w是可被确定的有限自是可被确定的有限自动机接受的。机接受的。742023/3/4 设计有限自动机设计有限自动机n自自动机的机的设计是一个是一个创造造过程，没有程，没有简单的算法或的算法或过程。程。n技巧：假技巧：假设自己是机器，思考如何去自己是机器，思考如

39、何去实现机器的任机器的任务。n为判断到目前判断到目前为止所看到的字符串是否止所看到的字符串是否满足某个足某个语言，言，须估估算出算出读一个字符串一个字符串时需要需要记住哪些关住哪些关键的的东西。西。例：例：构造自构造自动机，机，识别所有由奇数个所有由奇数个a和奇数个和奇数个b组成的字符串。成的字符串。关关键：不需要：不需要记住所看到的整个字符住所看到的整个字符串串，只需，只需记住至此所看到住至此所看到的的a、b个数是偶数个数是偶数还是奇数。是奇数。752023/3/4 q偶a偶bq奇a偶bq偶a奇bq奇a奇bStartbaabaabb第二节第二节不确定的有限自动机不确定的有限自动机(NFA)修

40、改修改DFA的模型，使之在某个状的模型，使之在某个状态，对应一个一个输入，入，可以有多个可以有多个转移，移，到达不到达不同的状同的状态，则称称为不确定的有不确定的有限自限自动机。机。例：例：762023/3/4(1)(2)一、不确定有限自动机的形式定义一、不确定有限自动机的形式定义nNFA是一个五元是一个五元组组，M=(Q,T,q0,F)。其中其中是是QT-2Q的函数，其余与的函数，其余与DFA相同。相同。n如果接收一个字符串后如果接收一个字符串后NFA进进入一个状入一个状态态集，集，而此集合中包含而此集合中包含一个以上一个以上F中的状中的状态态，则则称称NFA接收接收该该字符串。字符串。77

41、2023/3/4 782023/3/4(1)(2)pq r0 q q q,r 1pq r0 p r r 1 p,q 转移移图和和转移表表示的移表表示的NFA格局示例格局示例n如如图所示，用格局序列描述自所示，用格局序列描述自动机的工作机的工作过程，程，当当输入字符串是入字符串是011011时，则有有792023/3/4 二二、NFA的状态转移函数的状态转移函数与与DFA唯一不同之处唯一不同之处 :Q 2Q同同样样，可可扩扩展展为为(:Q T*2Q)1.(q,)=q含义：不允许无输入的状态变化。2.(q,a)=p|存在存在r(q,)p(r,a)n含含义义:(q,a)对对应应的的状状态态集集合合是

42、是(q,)对对应应的的每每个个状状态态下再下再接收字符接收字符a以后可能到达的状以后可能到达的状态态集合的并集集合的并集.即即若若(q,)=r1,r2,rk,则 (q,a)=(ri,a)其中其中 T*,a T，ri Q802023/3/4 812023/3/4 举例举例(p,)=p(p,0)=q(p,01)=q,r(p,010)=q(p,0100)=q(p,01001)=q,rpq r0 q q q,r 1扩展展转移函数适合于移函数适合于输入字符串入字符串822023/3/4 NFA接受的接受的语言言设一个设一个NFAA=(Q,T,q0,F)定义定义A的语言的语言:L(A)=w (q0,w)F

43、 第三节第三节NFA与与DFA的等价性的等价性nDFA是是NFA的特例，所以的特例，所以NFA必然能接收必然能接收DFA能接收能接收的的语语言。言。因此因此证证明等价性只要能明等价性只要能够证够证明一个明一个NFA所能所能接收的接收的语语言必能被另一个言必能被另一个DFA所接收所接收。1.定理：定理：设设一个一个NFA接受接受语语言言L，那么必然存在一个，那么必然存在一个DFA接受接受L。2.证证明明:n策策略略：对对于于任任意意一一个个NFA，构构造造一一个个接接收收它它所所能能接接收收语语言言的的DFA，这这个个DFA的的状状态态对对应应了了NFA的的状状态态集合。集合。832023/3/

44、4 842023/3/4 从从NFA构造等价的构造等价的DFA(子集构造法子集构造法)设设L是是某某个个NFAMN=(QN,T,N,q0,FN)的的语语言言,则则存在一个存在一个DFAMD,满足满足 L(MD)=L(MN)=L.证明证明:定义定义MD=(QD,T,D,q0,FD),其中其中 QD=S S QN=2Q 对对 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|可可证上述命题证上述命题.q S852023/3/4 pq r0 q q q,r 10 q 1 p q r

45、 p,q p,r q,r p,q,r q q,r q q,r q q q,r q q,r 子集构造法子集构造法举例例862023/3/4 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 子集构造法子集构造法举例例872023/3/4 证明明:从从NFA构造等价的构造等价的DFA设设MN=(QN,T,N,q0,FN)是一个是一个NFA,通过子集构造法通过子集构造法得到相应的得到相应的DFAMD=(QD,T,D,q0,FD),则则 对任何对任何w T*,D(q0,w)=N(q0,w).证明证明:归纳于归纳于|

46、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=1k882023/3/4 实践中实践中,通过子集构造法得到的通过子集构造法得到的DFA的状态数目的状态数目与与原原NFA的状态数目的状态数目大体大体相当相当.在较坏的情况下在较坏的情况下,上述上述 DFA的状态数目接近于所有子的状态数目接近于所有子集的数目集的数目.举例举例

47、由如下由如下 NFA构造的构造的 DFA的状态数目至少为的状态数目至少为2n子集构造法得到的状子集构造法得到的状态数数q0q1q2qn第四节第四节有有 转换的转换的NFAn一、定一、定义概念：当概念：当输入空串入空串(无无输入入)时，也能引，也能引起状起状态的的转移。移。例：892023/3/4 输入入“002”时的的转移格局：移格局：q0q1q2012902023/3/4 -NFA的形式定义的形式定义一个一个-NFA是一个五元组是一个五元组A=(Q,T,q0,F).有限状态集有限状态集 有限输入符号集有限输入符号集 转移函数转移函数 一个开始状态一个开始状态 一个终态集合一个终态集合q0 Q

48、 F Q与与NFA的不同之处的不同之处 :Q(T )2Q912023/3/4 -NFA如何接受输入符号串如何接受输入符号串q1q0q2q3q5 ,+,q4该该 -NFA可以接受的字符串如：可以接受的字符串如：3.14+.314314.922023/3/4 二、二、-闭包（闭包（closure）概念概念状态状态q的的-闭包闭包，记为，记为 -CLOSURE或或ECLOSE，定义为从，定义为从 q经所有的经所有的 路径可以到达路径可以到达的状态（包括的状态（包括q自身），自身），如：如：q0q1q2012-CLOSURE(q0)=q0,q1,q2-CLOSURE(q1)=q1,q2-CLOSURE

49、(q2)=q2状状态子集子集I I 的的-闭包：包：-CLOSURE(I)-CLOSURE(q)q I例：例：-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/4 942023/3/4 例：例：I Iq0q0，q1q1，求求I I1 1I I1 1 -CLOSURE-CLOSURE（I I，1 1）-CLOS

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