第3章自动机基础优秀课件.ppt

《第3章自动机基础优秀课件.ppt》由会员分享，可在线阅读，更多相关《第3章自动机基础优秀课件.ppt（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第3章 自动机基础第1页，本讲稿共40页3.1正规语言及其描述方法正规语言及其描述方法 【定义】【定义】正规语言正规语言是指由是指由正规文法正规文法定义的语言；定义的语言；程序设计语言中的程序设计语言中的单词单词，大都属于此种语言。，大都属于此种语言。正规语言有三种等价的表示方法：(1)正规文法 (2)正规式 (3)有限自动机正规文法仅有三种形式的产生式：(1)A-aB (2)A-a (3)A-【例【例3.1】G(Z)：A-aA|A=;A=aA=aaA=aaaA=an,n0L(G)=an|n0正规文法正规语言第2页，本讲稿共40页 正规语言判定示例正规语言判定示例:【例【例3.2】L1=amb

2、n|m0,n1,正规语言正规语言?可由正规文法定义：可由正规文法定义：G1(S):S-aS|bA;A-bA|L1是正规语言。是正规语言。【例【例3.3】L2=(ab)n|n1,正规语言正规语言?可由正规文法定义：可由正规文法定义：G2(S):S-aA;A-bB;B-aA|L2是正规语言。是正规语言。【例【例3.4】L3=anbn|n0,正规语言正规语言?不能由正规文法定义不能由正规文法定义(正规文法无法描述正规文法无法描述a和和b数数量上相等！量上相等！)：L3不是正规语言！不是正规语言！第3页，本讲稿共40页3.1.1正规语言正规语言的另外两种表示方法的另外两种表示方法.正规式表示法：正规式

3、表示法：正规式正规式是指由字母表中的符号，通过以下是指由字母表中的符号，通过以下三种运算三种运算(也可以使用圆括号也可以使用圆括号)连接起来构成的表连接起来构成的表达式达式e：闭包闭包(*(*，+)+)连接连接(.)(.)或或(|)(|)设设val(e),L(e)分别表示正规式分别表示正规式e的的值值和和语言，语言，则：则：L(e)=x|x=val(e)即即 正规式表示的语言是该正规式所有值的集合。正规式表示的语言是该正规式所有值的集合。正规式L3=abnc,bn|n0，L2=(ab)n|n1，e2=(ab)+e3=ab*c|b*L1=ambn|m0,n1，e1=a*b+第4页，本讲稿共40页

4、.有限自动机表示法：有限自动机表示法：L3=abnc,bn|n0L2=(ab)n|n1L1=ambn|m0,n1+b-ab+b-aa+-abcbb-FA1:FA2:FA3:初看起来，有限自动机是带标记的有向图！初看起来，有限自动机是带标记的有向图！3.1.1正规语言正规语言的另外两种表示方法的另外两种表示方法第5页，本讲稿共40页1,2,3,4状态集状态集;其中：其中：+(开始状态开始状态)；-(结束状态结束状态)a,b,c字母表字母表；(1,a)=2变换变换(或或);(表示表示1状态遇符号状态遇符号a变到变到2状态状态,)；有限自动机有限自动机表示法说明：表示法说明：aL3=abnc,bn|

5、n0+-abcbb-一个一个FA，若存在一条从某开始状态，若存在一条从某开始状态i到某结束状态到某结束状态j的通路，且这条通路上所有边的标记连成的符号串为的通路，且这条通路上所有边的标记连成的符号串为，则，则 就是一个句子；就是一个句子；所有这样的所有这样的 的集合，就是该的集合，就是该FA表示的语言表示的语言。【图符说明】：【图符说明】：【运行机制】：【运行机制】：第6页，本讲稿共40页FA:e=ab*c|b*G(S):S-aA|bB|，A-bA|c，B-bB|正规语言的三种表示法综合示例：正规语言的三种表示法综合示例：【例【例3.5】L=abnc,bn|n0,=a,b,c；【注】凡是能由上

6、述三种方法中的一种表示的语言，一定是正规语言；反之，凡是不能由上述三种方法表示的语言，一定不是正规语言。1.正规文法描述：正规文法描述：2.正规式描述正规式描述:3.有限自动机描述：有限自动机描述：+-abcbb-第7页，本讲稿共40页 3.2.1 有限自动机的定义状态状态i遇符号遇符号a时时变换为状态变换为状态j3.2有限自动机的定义和分类有限自动机的定义和分类 变换变换(二元函数二元函数);Q(有限状态集有限状态集);ija或或【定义】【定义】有限自动机是一种数学模型，用于描述有限自动机是一种数学模型，用于描述正规语言正规语言,可定义为五元组：可定义为五元组：FA=(Q,S,F,)(i,a

7、)=j其中：i,jQ,a+;F(结束状态集结束状态集,F Q);S(开始状态集开始状态集,S Q);(字母表字母表);即：即：第8页，本讲稿共40页L(FA)=x|ij,x*,iS,jFFA存在一条从某初始状态存在一条从某初始状态i到某结束状态到某结束状态j的的连连续变换续变换，且，且每次变换每次变换(=)的边标记连成的符号串恰的边标记连成的符号串恰好为好为x；称称x为为FA接受，否则拒绝接受，否则拒绝。令令L(FA)为自动机为自动机FA所描述的正规语言；则所描述的正规语言；则则则L(FA)的生成的生成(或识别或识别)过程如下过程如下所示：所示：如右图有限自动机：如右图有限自动机：3.2.2

8、有限自动机所描述的语言=x+-abcbb-设设x=a1a2an，ai+a1=i1ia2=i2an=j则有即：即：含义是含义是:第9页，本讲稿共40页L(FA)的生成的生成(或识别或识别)过程示例：过程示例：+-abcbb-.第一条通路：第一条通路：FA1=b+=a=b=c+=a=b=b=c.第二条通路：第二条通路：FA2+=a=c+=b=b+L(FA)=abnc,bn|n0L(FA1)=abnc|n0L(FA2)=bn|n0因而接受空串的 FA的典型特征！第10页，本讲稿共40页【例【例3.6】有限自动机】有限自动机：FA=(Q,S,F,)其中其中:Q=1,2,3,4,=a,b,c,S=1,2

9、,F=3,4FA的两种表现形式：的两种表现形式：状态转换图状态转换图:3.2.3 有限自动机的两种表现形式：(1,a)=2;(1,b)=4;(2,b)=2;(2,c)=3;(2,)=3;(4,b)=4;变换表变换表:变换表结构变换表结构：行行(状态状态)，列列(符号符号)，表项表项(变换后状变换后状态态)+-abcbb-+4 3 3 2 4 21234abc+-+开始状态结束状态第11页，本讲稿共40页【例【例3.7】A=abnc,(ab)n|n0二:变换函数不单值(如一:开始状态不唯一,不好用!(1,a)=(2|4),也不好用！3.2.4 有限自动机的分类方法一方法一：联合式联合式方法二方法

10、二：组合式组合式1 1方法三方法三：组合式组合式2 2+abc-+ab-比较之：+abc-ab-的有限自动机构造：的有限自动机构造：三:带有边，还是不好用!有好用的吗?!？+abc-ab-【例3.7】构造正规语言+abc-aba-第12页，本讲稿共40页 3.2.4 有限自动机的分类【有限自动机分类】【有限自动机分类】1.确定的有限自动机确定的有限自动机(DFA)特征特征：开始状态唯一开始状态唯一;变换函数单值变换函数单值;不带不带 边。边。2.非确定的有限自动机非确定的有限自动机(NFA)(1)带有带有 边的边的非确定的有限非确定的有限自动机自动机(NFA)(2)不带有不带有 边的边的非确定

11、的有限非确定的有限自动机自动机(NFA)-不能全部满足上述特征者！不能全部满足上述特征者！确定的有限自确定的有限自动机如右图所示：动机如右图所示：+abb-bcb-aa-ccDFA:A=abnc,(ab)n|n0第13页，本讲稿共40页3.3有限自动机的等价转换有限自动机的等价转换 有限自动机的有限自动机的等价转换等价转换,主要包含两个内容：主要包含两个内容：(1)有限自动机的确定化有限自动机的确定化(NFA=DFA);(2)有限自动机的最小化(DFA=最小的DFA);非确定机(NFA)较易构造，但不好用！确定机(DFA)较难构造，但好用！任何一非确定机NFA，皆可通过有效算法把其转化为等价的

12、确定机DFA（二者描述的语言相同）。有限自动机的最小化,又称有限自动机的化简；是指：对给定的确定机DFA1,构造另一个确定机DFA2,使得 L(DFA1)=L(DFA2),且DFA2的状态最少。第14页，本讲稿共40页 ab*,b+,L(FA2)=abn,bn|n0 【定义1】设有两个有限自动机FA1和FA2，若L(FA1)=L(FA2)则称FA1与FA2等价，记作FA1FA2。3.3.1 有限自动机的等价.两个自动机的等价：两个自动机的等价：+ab-bFA2FA1L(FA1)=L(FA2)+ab-bb-FA1 FA2四条四条通路，分别接受：通路，分别接受：ab+,ab*,b+,L(FA1)=

13、abn,bn|n0二条二条通路，分别接受：通路，分别接受：第15页，本讲稿共40页.两个状态的等价：两个状态的等价：【定义2】设 i 和 j 为FA的两个状态，若把其看作初态，二者接受的符号串集合相同，则有 i j(等价)。3.3.1 有限自动机的等价【例2】FA2+abc-【例1】FA1:+abc-【注】如何判断两个状态的等价性？稍后再讨论。2 4？3 5？4 5？判断等价性：2 3？2,3节点构成节点构成 闭路闭路2,3等价等价；可；可合而为一合而为一a-ba-a第16页，本讲稿共40页(3)对对 边，按边，按 通路通路逆向逆向逐一进行：逐一进行：3.3.2有限自动机的确定化算法有限自动机

14、的确定化算法.消除消除 边算法边算法(NFA=或或DFA):NFA(1)若存在若存在 闭路，闭路，则把则把 闭路上各节闭路上各节点点合而为一：合而为一：abc-abc-(2)标记标记隐含的隐含的开始态开始态和和结束态：结束态：开始态的开始态的 通路通路上的节点：上的节点：+结束态结束态逆向逆向 通路通路上节点：上节点：-删除一个删除一个 边；同时边；同时 引进引进新边新边 ：凡由凡由原原 边终点边终点发出的边，也要由发出的边，也要由其始点其始点发出。发出。(4)重复步骤重复步骤(3)，直到再无，直到再无 边边为止。为止。+cb-b+-abbcc第17页，本讲稿共40页am,ambcn,amcn

15、|m0,n1L()=NFA(2)标记标记隐含的隐含的开始态开始态和和结束态结束态：L(NFA)=?消除消除 边算法示例：边算法示例：【例【例3.8】考查】考查 NFA：+abc-(1)闭路上的节点闭路上的节点等价等价（）,可可合而为一；合而为一；(3)逆序逐一逆序逐一删除删除 边，边，同时同时引进引进新边：新边：abc-+-+abc-+c-+abc-+cc-+NFA+-+，+，第18页，本讲稿共40页3.3.2有限自动机的确定化算法有限自动机的确定化算法(续续1).把把 化为化为DFADFA算法算法(=DFA):NFANFA(2)按 的变换函数实施变换：NFA(qi1,qin,ak)=(qi1

16、,ak)(qin,ak)=qj1,qjn(3)若若qj1,qjn未作为未作为状态行状态行标记，则作新行标记；标记，则作新行标记；a1a2a3q01,q0n(4)重复步骤重复步骤(2)(3)，直到不再出现新状态集为止；，直到不再出现新状态集为止；(5)标记标记DFA的的开始态开始态和和结束态结束态：第一行第一行q01,q0n，(右侧右侧)标记标记+；凡是凡是状态行状态行中含有中含有的的结束状态结束状态者，者，(右侧右侧)标记标记-【注】【注】必要时，新产生的必要时，新产生的DFA可用状态图表示。可用状态图表示。NFA字母表中符号 开始态集NFA(1)构造构造DFA的变换表的变换表(框架框架)：第

17、19页，本讲稿共40页确定化示例：确定化示例：NFA+abc-+ab-【例【例3.9】联合】联合式自动机式自动机NFA:确定化过程确定化过程:DFA:cb aD3F2E5C2,4G4E5D3F2F2E5G4D3D3C2,4B2,5B2,5+-ABCEFGD+-acbabcc-bba-【注】【注】A,B,C,状态集的代码状态集的代码A1,4第20页，本讲稿共40页NFA确定化练习确定化练习1.消除 边练习2.确定化练习NFA第21页，本讲稿共40页1.消除 边练习的答案2.确定化练习的答案NFANFA确定化练习确定化练习011223334,5,64,5,63773第22页，本讲稿共40页3.3.

18、3有限自动机的最小化算法有限自动机的最小化算法 最小有限自动机，是指满足下述条件的确定最小有限自动机，是指满足下述条件的确定有限自动机：有限自动机：(1)没有无用状态没有无用状态(无用状态已删除无用状态已删除)；(2)没有等价状态没有等价状态(等价状态已合并等价状态已合并)。.删除无用状态算法删除无用状态算法 【定义】【定义】无用状态无用状态是指自动机从开始态出发，对是指自动机从开始态出发，对任何符号串都不能到达的状态。任何符号串都不能到达的状态。【判别算法】【判别算法】构造有用状态集构造有用状态集Qus(1)设设q0为开始态，则为开始态，则令令q0Qus；(2)若若qiQus且有且有(qi,

19、a)=qj则令则令qjQus；(3)重复执行重复执行(2)，直到，直到Qus不再增大为止。不再增大为止。(4)从状态集从状态集Q中，删除不在中，删除不在Qus中的所有状态。中的所有状态。第23页，本讲稿共40页3.3.3有限自动机的最小化算法有限自动机的最小化算法(续续1).合并等价状态算法合并等价状态算法【原理】两个状态【原理】两个状态i,j等价，当且仅当满足下面两等价，当且仅当满足下面两个条件：个条件：必须必须同是同是结束态结束态，或，或同不是同不是结束态结束态；对对所有所有字母表上符号，状态字母表上符号，状态i,j必变必变换到等价状态。换到等价状态。【例】把下述自动机最小化：【例】把下述

20、自动机最小化：(1)初分成两个不等价子集：初分成两个不等价子集：Q1=1,2,Q2=3(2)还能分成不等价子集吗？还能分成不等价子集吗？(1,a)=2,(2,a)=2又又(1,b)=3,(2,b)=3+-babaa12(等价等价)合并后的最小自动机+-aba第24页，本讲稿共40页3.3.3有限自动机的最小化算法有限自动机的最小化算法(续续2).合并等价状态算法合并等价状态算法(1)初始，把状态集初始，把状态集Q划分成两个不等价子集划分成两个不等价子集:Q1(结束状态集结束状态集)，Q2(非结束状态集非结束状态集)；(2)把每个把每个Qi再划分成不同的子集，条件是：再划分成不同的子集，条件是：

21、对同一对同一Qi中两个状态中两个状态i和和j，若对字母表中，若对字母表中的的某个某个符号，变换到符号，变换到已划分已划分的不同的状态集中，的不同的状态集中，则则i和和j应分离应分离:(3)重复步骤重复步骤(2)，直到再不能划分为止；，直到再不能划分为止；(4)合并最终划分的每个子集中的各状态合并最终划分的每个子集中的各状态(合而为一合而为一)。如如(i,a)Qm,(j,a)Qn且且mn-划分不等价状态集划分不等价状态集第25页，本讲稿共40页有限自动机化简示例有限自动机化简示例【例【例3.10】化简下述化简下述DFA:(1)删除无用状态：删除无用状态：动态构造动态构造DFA变换表变换表，即从开

22、始状态，即从开始状态1出发，出发，把变换后的状态填入表项，并同时作为新行标记；把变换后的状态填入表项，并同时作为新行标记；如此下去，直到再不出现新状态为止。未出现的状如此下去，直到再不出现新状态为止。未出现的状态，就是无用的状态。态，就是无用的状态。【注】【注】DFA中的状态中的状态2，8被删除被删除!4647375644513361ba+-+-bababababaaabaDFA的变换表：的变换表：第26页，本讲稿共40页 有限自动机化简示例有限自动机化简示例(续续1)1)4647375644513361ba+-DFA:(2)合并等价状态合并等价状态:令令QNE=1,3,4,5,6,7取取1,

23、3,4：即即QNE=1,3,4,5,6,7取取3,4：(3,a)=1,(4,a)=4划分划分Q1=3,Q2=4即即QNE=1,3,4,5,6,7取取5,6,7:同理，可划分成同理，可划分成Q1=5,Q2=6,7；最后：最后：QNE=1,3,4,5,6,7不等价集(1,a)=6,(3,4,a)=1,4划分成划分成Q1=1,Q2=3,4第27页，本讲稿共40页有限自动机化简示例有限自动机化简示例(续续2)4647375644513361ba+-DFA:合并等价状态合并等价状态:6,746365644513361ba+-+-babbabaaa6替换替换7最小的DFA!第28页，本讲稿共40页有限自动

24、机化简练习有限自动机化简练习删除无删除无用状态用状态合并等合并等价状态价状态第29页，本讲稿共40页(3)令令getchar(ch)为读符号函数。为读符号函数。3.4有限自动机的实现有限自动机的实现 用计算机完成有限自动机的功能，其核心是用计算机完成有限自动机的功能，其核心是“变换变换”的的实现技术。这里介绍的是把实现技术。这里介绍的是把变换表变换表按某种方式存储起来，按某种方式存储起来，作为知识源来识别单词，实现机制是：作为知识源来识别单词，实现机制是：控制程序 变换表+【三点说明】【三点说明】(1)假定自动机只作为假定自动机只作为识别器识别器，即，即对对待识别的待识别的符号串符号串：仅回答

25、仅回答是是(接受接受)或或否否(拒绝拒绝)。(2)为便于处理，可令为便于处理，可令#作为作为待识别的待识别的符号串符号串的的后继符后继符。为此，扩展自动机如下：为此，扩展自动机如下：+-a-b-#ok 4ok 5 6 3 1#b a+-空则no第30页，本讲稿共40页3.4.1 控制程序设计开始结束state=1getchar(ch)查变换表：(state,ch)=?=空 =ok回答:yes回答:noynystate=n开始状态1赋给变量 state从输入串中读取一符号到变量 ch 变量 state 重新被赋值为变换后的状态！第31页，本讲稿共40页 n3.4.2 变换表存储结构设计变换表的存

26、储结构可选择下述两种方式之一：变换表的存储结构可选择下述两种方式之一：(1)二维数组二维数组，其下标是其下标是(状态，输入符号状态，输入符号)；为了适应不同编码语言的需要，状态和输入为了适应不同编码语言的需要，状态和输入符号可采取相应的符号可采取相应的编码形式编码形式；通常，使用连续通常，使用连续的正整数：的正整数：0,1,2,3,。(2)压缩变换表压缩变换表，方法是把每个状态行作为，方法是把每个状态行作为子表，状态子表，状态为索引，为索引，并把并把错误的输入符号合并在一起，如：错误的输入符号合并在一起，如：nobanofenoyx索引表索引表(其他其他)-错误符号。错误符号。状态变换子表第3

27、2页，本讲稿共40页有限自动机实现示例有限自动机实现示例【例【例3.11】有限自动机有限自动机DFA:+ab-#abcdnobanodnocbanook#压缩变换表输入串输入串aacd#识别过程：识别过程：备注变换剩余chstate3acd#a1接受ok#44#d22d#c33cd#a3索引表索引表第33页，本讲稿共40页3.5正规语言描述方法间的相互转换正规语言描述方法间的相互转换 正规语言有三种等价的表示方法：(1)正规文法 (2)正规式 (3)有限自动机 我们以有限自动机为核心，介绍彼此间的转换关系：.正规文法正规文法DFA设设G(Z)=(VN,VT,Z,P),DFA=(Q,S,F,)则

28、有：VT(A,a)=BA-aB(A,a)=B(结束态)A-aS(开始态)Z(开始符号)QVNDFA正规文法A-A(结束态)有时需要增加一个结束状态有时需要增加一个结束状态第34页，本讲稿共40页Z-aZ|bA|,A-bA|dB,B-正规文法与正规文法与DFA间转换示例：间转换示例：【例【例3.12】自动机自动机=正规文法正规文法:abcd+-DFA:令令Z-,A-,B-则有正规文法则有正规文法Z-aA|cB,A-bA|dB,B-【例【例3.13】正规文法正规文法=自动机自动机,并求并求L(G):G(Z):Z-aZ|bA|,A-bA|dA-d可变换为可变换为A-dB,B-G(Z)(与与G(Z)等

29、价等价):令令-Z,-A,-B对应的DFAbad+-b则则L(G)=am,ambnd|m0,n0G(Z):第35页，本讲稿共40页esfe+-.正规式正规式DFA设设e为正规式为正规式,DFA=(Q,S,F,)转换机制转换机制：e=DFA分解过程；分解过程；DFA=e合成过程。合成过程。开始态结束态则有：则有：合成合成分解分解ije1|e2ije1.e2ije*ije2e1ije1ke2ijekiejjeieiej实践中，可简化为其中一种：或或或或或或3.5正规语言描述方法间的相互转换正规语言描述方法间的相互转换第36页，本讲稿共40页正规式与正规式与DFA间转换示例：间转换示例：【例【例3.

30、14】正规式正规式=自动机自动机设设e=a*b|bc*则：则：a*bbc*+-a*c*+-bbac+-bb+-aac+-bbb+-aac+-bbb-+D9C3,9bB2B2D9E3C3,9B2A1,2caE3E3+-aacA+BbbD-CEc-等价!确定化DFA:第37页，本讲稿共40页正规式与正规式与DFA间转换练习间转换练习(1)1.(a*|b*)b(ba)*2.1(0|1)*101 第38页，本讲稿共40页正规式与正规式与DFA间转换练习间转换练习(1)答案答案1.(a*|b*)b(ba)*等价的DFA2.1(0|1)*101等价的DFA 第39页，本讲稿共40页正规式与正规式与DFA间转换练习间转换练习(2)写出与以下DFA等价的正规式ab0+12-bbaaa*b0+12-bab*aa*bab*0+12-ab*aba*ba*b(ab*a|ba*b)*ab*0+2-R=a*b(ab*a|ba*b)*ab*第40页，本讲稿共40页