第3章__自动机基础

1、第第3 3章章 自动机基础自动机基础 自动机是一种语言模型，是语言的一种自动机是一种语言模型，是语言的一种识别工具识别工具，其中的其中的 有限自动机有限自动机(Finite Automata) FA被用来处理被用来处理正规语言正规语言，后者是编译程序设计中后者是编译程序设计中词法分词法分析析的对象。的对象。3.1 正规语言正规语言及其描述方法及其描述方法3.2 有限自动机有限自动机的定义与分类的定义与分类3.3 有限自动机的有限自动机的等价转换等价转换3.4 有限自动机的有限自动机的实现实现3.5 正规语言描述方法间的相互正规语言描述方法间的相互转换转换3.1 正规语言及其描述方法正规语言及其

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

3、定示例正规语言判定示例: :【例【例3.2】 L1 = ambn| 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数数量上相等！

4、量上相等！)： L3 不是正规语言！不是正规语言！ 3.1.1 正规语言的另外两种表示方法. 正规式表示法：正规式表示法： 正规式正规式是指由字母表中的符号，通过以下是指由字母表中的符号，通过以下三种运算三种运算(也可以使用圆括号也可以使用圆括号)连接起来构成的表达连接起来构成的表达式式 e ： 闭包闭包( ( * *，+) +) 连接连接 ( .) ( .) 或或( | )( | ) 设设 val(e),L(e) 分别表示正规式分别表示正规式 e 的的值值和和语言，语言，则：则： L(e)= x| x=val(e)即即 正规式表示的语言是该正规式所有值的集合。正规式表示的语言是该正规式所有值

5、的集合。正规式正规式 L3= abnc, bn | n0 ， L2= (ab)n| n1 ，e2=(ab)+e3= ab*c|b* L1= ambn| m0 ,n1 ，e1= a*b+. 有限自动机表示法：有限自动机表示法： L3= abnc ,bn|n0 L2= (ab)n|n1 L1= ambn| m0 ,n1 + + b- -ab+ + b- -aa+-abcbb-FA1:FA2:FA3: 初看起来，有限自动机是带标记的有向图！初看起来，有限自动机是带标记的有向图！3.1.1 正规语言的另外两种表示方法 1,2,3,4 状态集状态集; 其中：其中： +(开始状态开始状态)； -(结束状态

6、结束状态) a,b,c 字母表字母表； (1,a)=2 变换变换 ( 或或 );(表示表示1状态遇符号状态遇符号a变到变到2状态状态,)；有限自动机有限自动机表示法说明：表示法说明： aL3= abnc ,bn|n0 +-abcbb- 一个一个FA，若存在一条从某开始状态，若存在一条从某开始状态 i 到某结束状态到某结束状态 j 的通路，且这条通路上所有边的标记连成的符号串的通路，且这条通路上所有边的标记连成的符号串为为 ，则，则 就是一个句子；就是一个句子；所有这样的所有这样的 的集合，就是的集合，就是该该 FA 表示的语言表示的语言。【图符说明】：【图符说明】：【运行机制】：【运行机制】：

7、FA:e = ab*c|b* G(S): S- aA|bB| ，A - bA|c ，B - bB| 正规语言的三种表示法综合示例：正规语言的三种表示法综合示例：【例【例3.5】 L = abnc, bn| n0 ,= a,b,c； 【注】凡是能由上述三种方法中的一种表示的语言，一定是正规语言；反之，凡是不能由上述三种方法表示的语言，一定不是正规语言。1. 正规文法描述：正规文法描述： 2. 正规式描述正规式描述:3. 有限自动机描述：有限自动机描述：+-abcbb- 3.2.1 有限自动机的定义状态状态 i 遇符号遇符号 a 时时变换为状态变换为状态 j 3.2 有限自动机的定义和分类有限自动

8、机的定义和分类 变换变换(二元函数二元函数) ;Q(有限状态集有限状态集) ; i ij ja a或或【定义】【定义】 有限自动机是一种数学模型，用于描述有限自动机是一种数学模型，用于描述正规语言正规语言, ,可定义为五元组：可定义为五元组： FA=( Q , , S , F , ) (i , a)= j其中：其中：i , jQ, a+ ;F(结束状态集结束状态集, F Q) ;S(开始状态集开始状态集, S Q) ; (字母表字母表) ;即：即：L(FA)= x| i j , x* ,iS,jF FA 存在一条从某初始状态存在一条从某初始状态 i 到某结束状态到某结束状态 j 的的连连 续变

9、换续变换，且，且每次变换每次变换(=)的边标记连成的符号串恰好的边标记连成的符号串恰好为为 x ；称称x为为FA接受，否则拒绝接受，否则拒绝。 令令L(FA)为自动机为自动机FA所描述的正规语言；则所描述的正规语言；则 则则 L(FA)的生成的生成(或识别或识别)过程如下过程如下所示：所示： 如右图有限自动机：如右图有限自动机： 3.2.2 有限自动机所描述的语言有限自动机所描述的语言= x x+-abcbb-设设 x=a1 a2an ， ai+ a a1 1=i1ia a2 2=i2a an n=j则有则有即：即：含义是含义是: : L(FA)的生成的生成(或识别或识别)过程示例：过程示例：

10、+-abcbb-.第一条通路：第一条通路：FA1=b b+ + +=a a =b b=c c+ +=a a =b b =b b=c c.第二条通路：第二条通路：FA2+ += =a a =c c+ +=b b =b b+ + L(FA)=abnc, bn| n0 L(FA1)= abnc| n0 L(FA2)= bn| n0 因而因而接受空串的接受空串的 FA的典型特征！的典型特征！【例【例3.6】有限自动机】有限自动机 ：FA=( Q,S,F, ) 其中其中: Q=1,2,3,4,=a,b,c, S=1,2, F=3,4 FA 的两种表现形式：的两种表现形式： 状态转换图状态转换图: : 3

11、.2.3 有限自动机的两种表现形式有限自动机的两种表现形式 ：(1,a)=2; (1,b)=4;(2,b)=2; (2,c)=3; (2, )=3; (4,b)=4; 变换表变换表: : 变换表结构变换表结构：行行(状态状态)，列列(符号符号)，表项表项(变换后状态变换后状态) +-abcb bb b- + + 4 3 3 2 4 21234a bc + +- - -+ +开始状态开始状态结束状态结束状态 【例【例3.7】A= abnc,(ab)n|n0 二二: 变换函数不单值变换函数不单值(如如一一: 开始状态不唯一开始状态不唯一,不好用不好用! (1,a)=(2|4),也不好用！也不好用！

12、 3.2.4 有限自动机的分类有限自动机的分类方法一方法一：联合式联合式方法二方法二：组合式组合式1 1方法三方法三：组合式组合式2 2+ab bc-+ab b-比较之：比较之：+ab bc- ab b-的有限自动机构造：的有限自动机构造：三三: 带有带有 边，还是不好用边，还是不好用!有好用的吗有好用的吗?!?!？+ab bc-a ab b-【例【例3.73.7】构造正规语言】构造正规语言+ab bc-a ab ba a- 3.2.4 有限自动机的分类有限自动机的分类【有限自动机分类】【有限自动机分类】1. 确定的有限自动机确定的有限自动机(DFA)特征特征：开始状态唯一开始状态唯一; 变换

13、函数单值变换函数单值; 不带不带 边。边。2. 非确定的有限自动机非确定的有限自动机(NFA)(1) 带有带有 边的边的非确定的有限非确定的有限自动机自动机( NFA)(2) 不带有不带有 边的边的非确定的有限非确定的有限自动机自动机( NFA)- 不能全部满足上述特征者！不能全部满足上述特征者！ 确定的有限自确定的有限自动机如右图所示：动机如右图所示：+abb-bcb-aa-ccDFA: A= abnc,(ab)n|n0 3.3 有限自动机的等价转换有限自动机的等价转换 有限自动机的有限自动机的等价转换等价转换, ,主要包含两个内容：主要包含两个内容：(1) 有限自动机的确定化有限自动机的确

14、定化( NFA=DFA);(2) 有限自动机的最小化有限自动机的最小化( DFA=最小的最小的DFA); 非确定机非确定机(NFA) 较易构造较易构造，但不好用！但不好用！ 确定机确定机 (DFA) 较难构造，但好用！较难构造，但好用！ 任何一非确定机任何一非确定机NFA，皆可通过有效算，皆可通过有效算法把其转化为等价的确定机法把其转化为等价的确定机DFA（二者描（二者描述的语言相同）。述的语言相同）。 有限自动机的有限自动机的最小化最小化, ,又称有限自动机的又称有限自动机的化简化简；是；是指：指：对给定的确定机对给定的确定机DFA1,构造另一个确定机构造另一个确定机DFA2,使得使得 L(

15、DFA1)=L(DFA2),且且DFA2的状态最少。的状态最少。 ab* , b+ , L(FA2)=abn,bn|n0 【定义【定义1】设有两个有限自动机】设有两个有限自动机FA1和和FA2，若，若L(FA1)= L(FA2)则称则称FA1与与FA2等价，记作等价，记作FA1 FA2。 3.3.1 有限自动机的有限自动机的等价等价. 两个自动机的等价：两个自动机的等价：+ab b- b b FA2FA1 L(FA1)=L(FA2)+ +ab b-b bb b- FA1 FA2四条四条通路，分别接受：通路，分别接受： ab+ , ab* , b+ , L(FA1)=abn,bn|n0二条二条通

16、路，分别接受：通路，分别接受： . . 两个状态的等价：两个状态的等价： 【定义【定义2】设】设 i 和和 j 为为FA的两个状态，若把其的两个状态，若把其看作初看作初态态，二者接受的符号串集合相同，则有，二者接受的符号串集合相同，则有 i j (等价等价)。 3.3.1 有限自动机的有限自动机的等价等价【例【例2】FA2+ab bc- 【例【例1】FA1:+ab bc-【注】如何判断两个状态的等价性？稍后再讨论。【注】如何判断两个状态的等价性？稍后再讨论。2 4 ？3 5 ？4 5 ？判断等价性：判断等价性：2 3 ？ 2,3节点构成节点构成 闭路闭路 2,3等价等价；可；可合而为一合而为一

17、a-b ba a- a a(3) 对对 边，按边，按 通路通路逆向逆向逐一进行：逐一进行：3.3.2 有限自动机的确定化算法有限自动机的确定化算法. 消除消除 边算法边算法( NFA = 或或DFA ): NFANFA(1) 若存在若存在 闭路，闭路，则把则把 闭路上各节闭路上各节点点合而为一：合而为一：ab bc- ab bc-(2) 标记标记隐含的隐含的开始态开始态和和结束态：结束态：开始态的开始态的 通路通路上的节点：上的节点：+ +结束态结束态逆向逆向 通路通路上节点：上节点：- - 删除一个删除一个 边；同时边；同时 引进引进新边新边 ：凡由凡由原原 边终点边终点发出的边，也要由发出

18、的边，也要由其始点其始点发出。发出。(4) 重复步骤重复步骤(3)，直到再无，直到再无 边边为止。为止。+c cb b-b b + + +- -ab bb bc cc c am,ambcn, amcn|m0,n1 L( )=L( )= NFANFA(2) 标记标记隐含的隐含的开始态开始态和和结束态结束态：L( NFA)= ? 消除消除 边算法示例：边算法示例：【例【例3.8】考查】考查 NFA： +ab bc c- (1) 闭路上的节点闭路上的节点等价等价（ ）, ,可可合而为一；合而为一； (3) 逆序逐一逆序逐一删除删除 边，边，同时同时引进引进新边：新边：ab bc c-+ + -+ +

19、ab bc c-+ + c c-+ +ab bc c-+ +c cc c-+ + NFANFA+ + + +- -+ +，+ +，3.3.2 有限自动机的确定化算法有限自动机的确定化算法(续续1).把把 化为化为DFADFA算法算法( ( =DFA ) ): : NFANFA NFANFA(2) 按按 的变换函数实施变换：的变换函数实施变换： NFANFA (qi1,qin ,ak)= (qi1, ak) (qin, ak)=qj1,qjn(3) 若若qj1,qjn 未作为未作为状态行状态行标记，则作新行标记；标记，则作新行标记；a1a2a3q01,q0n(4) 重复步骤重复步骤(2)(3)，

20、直到不再出现新状态集为止；，直到不再出现新状态集为止；(5) 标记标记DFA的的开始态开始态和和结束态结束态： 第一行第一行q01,q0n，(右侧右侧)标记标记 + ； 凡是凡是状态行状态行中含有中含有 的的结束状态结束状态者，者，(右侧右侧)标记标记 - 【注】【注】必要时，新产生的必要时，新产生的DFA可用状态图表示。可用状态图表示。 NFANFA字母表中符号字母表中符号 开始态集开始态集 NFANFA(1) 构造构造DFA的变换表的变换表(框架框架)： 确定化示例：确定化示例： NFA+abc-+ab-【例【例3.9】联合】联合式自动机式自动机NFA: 确定化过程确定化过程:DFA: c

21、b aD3F2E5C2,4G4E5D3F2F2E5G4D3D3C2,4B2,5B2,5+-ABCEFGD+-acbabcc-bba-【注】【注】A,B,C, 状态集的代码状态集的代码A1,4NFA确定化练习确定化练习1. 消除消除 边练习边练习2. 确定化练习确定化练习 NFANFA1. 消除消除 边练习的边练习的答案答案2. 确定化练习的确定化练习的答案答案 NFANFANFA确定化练习确定化练习01122333 4,5,64,5,6 3 7733.3.3 有限自动机的最小化算法有限自动机的最小化算法 最小有限自动机，是指满足下述条件的确定最小有限自动机，是指满足下述条件的确定有限自动机：有

22、限自动机：(1) 没有无用状态没有无用状态(无用状态已删除无用状态已删除)；(2) 没有等价状态没有等价状态(等价状态已合并等价状态已合并)。.删除无用状态算法删除无用状态算法 【定义】【定义】无用状态无用状态是指自动机从开始态出发，对是指自动机从开始态出发，对任何符号串都不能到达的状态。任何符号串都不能到达的状态。【判别算法】【判别算法】 构造有用状态集构造有用状态集 Qus(1) 设设 q0 为开始态，则为开始态，则 令令 q0Qus ；(2) 若若 qiQus 且有且有 (qi,a)= qj 则令则令 qjQus ； (3) 重复执行重复执行(2)，直到，直到Qus不再增大为止。不再增大

23、为止。(4) 从状态集从状态集Q中，删除不在中，删除不在Qus中的所有状态。中的所有状态。3.3.3 有限自动机的最小化算法有限自动机的最小化算法(续续1). . 合并等价状态算法合并等价状态算法【原理】两个状态【原理】两个状态i , j 等价，当且仅当满足下面两等价，当且仅当满足下面两个条件：个条件： 必须必须同是同是结束态结束态，或，或同不是同不是结束态结束态； 对对所有所有字母表上符号，状态字母表上符号，状态 i , j 必变必变换到等价状态。换到等价状态。【例】把下述自动机最小化：【例】把下述自动机最小化：(1) 初分成两个不等价子集：初分成两个不等价子集：Q1=1,2,Q2=3(2)

24、 还能分成不等价子集吗？还能分成不等价子集吗？ (1,a)= 2 , (2,a)= 2 又又 (1,b)= 3 , (2,b)= 3+ +- - -b ba ab ba aa a 12(等价等价)合并后的最合并后的最小自动机小自动机+ +- -a ab ba a3.3.3 有限自动机的最小化算法有限自动机的最小化算法(续续2). . 合并等价状态算法合并等价状态算法(1) 初始，把状态集初始，把状态集Q划分成两个不等价子集划分成两个不等价子集:Q1(结束状态集结束状态集)， Q2(非结束状态集非结束状态集)；(2) 把每个把每个Qi再划分成不同的子集，条件是：再划分成不同的子集，条件是： 对同

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

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

27、,4, 5,6,7 取取 1,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 有限自动机化简示例有限自动机化简示例(续续2)4647375644513361ba+-DFA:合并等价状态合并等价状态: 6 , 746365644513361b

28、a+-+- -babbabaaa 6替换替换7最小的最小的DFA ! 有限自动机化简练习有限自动机化简练习删除无删除无用状态用状态合并等合并等价状态价状态(3) 令令 getchar(ch) 为读符号函数。为读符号函数。3.4 有限自动机的实现有限自动机的实现 用计算机完成有限自动机的功能，其核心是用计算机完成有限自动机的功能，其核心是“变换变换”的实现技术。这里介绍的是把的实现技术。这里介绍的是把变换表变换表按某按某种方式存储起来，作为知识源来识别单词，实现机种方式存储起来，作为知识源来识别单词，实现机制是：制是： 控制程序控制程序 变换表变换表 +【三点说明】【三点说明】(1) 假定自动机

29、只作为假定自动机只作为识别器识别器，即，即对对待识别的待识别的符号串符号串： 仅回答仅回答 是是(接受接受) 或或 否否(拒绝拒绝)。 (2) 为便于处理，可令为便于处理，可令 # 作为作为待识别的待识别的符号串符号串的的后继符后继符。为此，扩展自动机如下：为此，扩展自动机如下：+-a-b-#ok 4ok 5 6 3 1# b a+-空则空则no3.4.1 控制程序设计控制程序设计开始开始结束结束state = 1getchar(ch)查变换表：查变换表： (state,ch)= ? =空空 =ok回答回答:yes回答回答:noynystate = n开始状态开始状态1赋给赋给变量变量 sta

30、te从输入串中读取一从输入串中读取一符号到变量符号到变量 ch 变量变量 state 重新重新被赋值为变换后被赋值为变换后的状态！的状态！ n3.4.2 变换表存储结构设计变换表存储结构设计变换表的存储结构可选择下述两种方式之一：变换表的存储结构可选择下述两种方式之一：(1) 二维数组二维数组 ，其下标是其下标是(状态，输入符号状态，输入符号)； 为了适应不同编码语言的需要，状态和输入为了适应不同编码语言的需要，状态和输入符号可采取相应的符号可采取相应的编码形式编码形式；通常，使用连续通常，使用连续的正整数：的正整数：0,1,2,3,。(2) 压缩变换表压缩变换表，方法是把每个状态行作为，方法

31、是把每个状态行作为子表，状态子表，状态为索引，为索引，并把并把错误的输入符号合并在一起，如：错误的输入符号合并在一起，如：nobanofenoyx索引表索引表 (其他其他)-错误符号。错误符号。状状态态变换子表变换子表 有限自动机实现示例有限自动机实现示例【例【例3.11】 有限自动机有限自动机DFA: +ab-#abcdnobanodnocbanook#压缩变换表压缩变换表输入串输入串 aacd# 识别过程：识别过程：备注变换剩余chstate3acd#a1接受ok#44#d22d#c33cd#a3索引表索引表3.5 正规语言描述方法间的相互转换正规语言描述方法间的相互转换 正规语言正规语言有三种等价的表示方法：有三种等价的表示方法： (1) 正规文法正规文法 (2) 正规式正规式 (3) 有限自动机有限自动机 我们以我们以有限自动机有限自动机为核心，介绍彼此间的转换关系：为核心，介绍彼此间的转换关系： . 正规文法正规文法 DFA设设 G(Z)=(VN,VT,Z,P), DFA=(Q,S,F, )则有：则有：VT(