编译原理第三章自动机基础(2)

1、【例例3.63.6】有限自动机有限自动机 ：FA=( Q,S,F,FA=( Q,S,F, ) ) 其中其中: : Q Q=1,2,3,4,=1,2,3,4,=a,b,c, =a,b,c, S S=1,2, =1,2, F F=3=3，44 FAFA 的两种表现形式：的两种表现形式： 状态图状态图: : ：(1,a)=2;(1,b)=4(1,a)=2;(1,b)=4；(2,b)=2(2,b)=2； (2,c)=3(2,c)=3；(2,(2, )=3)=3；(4,b)=4(4,b)=4； 变换表变换表: : 变换表结构变换表结构：行行( (状态状态),),列列( (符号符号),),表项表项( (变

2、换后状态变换后状态) ) +-abcb bb b- + +4332421 12 23 34 4a ab bc c + +- - -+ +开始状态开始状态结束状态结束状态a ab b【例例3.73.7】 A= ab A= abn nc,(ab)c,(ab)n n|n0 |n0 或或：变换函数不单值，如：变换函数不单值，如一一：开始状态不唯一：开始状态不唯一, ,不好用不好用! !( ( (1,a)=(2|4) ),(1,a)=(2|4) ),仍不好用！仍不好用！方法一方法一：联合式联合式方法二方法二：组合式组合式1 1比较：比较：二二：带有：带有 边，也不好用边，也不好用! !有好用的吗有好用的

3、吗?!?!FAFA的构造：的构造：+ab bc-+ -+ -ab b+ -+ -ab b+ab bc-或或+ab bc-【例例3.73.7】构造正规语言构造正规语言+ab bc-a ab ba a- A=ab A=abn nc,(ab)c,(ab)n n|n0 |n0 +ab bb b-b bcb b-aa-ccDFA:DFA: 确定的有确定的有限自动机如右图限自动机如右图所示：所示：方法三方法三：确定式确定式+ab bb b-b bcb b-aa-ccDFA:DFA: 确定的有限自动机确定的有限自动机(DFA)(DFA)特征特征：开始状态唯一：开始状态唯一; ; 变换函数单值；不带变换函数单

4、值；不带 边。边。 非确定的有限自动机非确定的有限自动机(NFA)(NFA) 带有带有 边的边的非确定的有限非确定的有限自动机自动机( ( NFA)NFA) 不带有不带有 边的边的非确定的有限非确定的有限自动机自动机( NFA)( NFA)- - 不能全部具备上述特征者！不能全部具备上述特征者！ 3.2.4 3.2.4 有限自动机的分类有限自动机的分类要领要领：构造的同时，：构造的同时，要考虑连接！要考虑连接！+ab b- b b FA1FA1+ +ab b-b bb b-【例例3.83.8 】试分别指出下述有限自动机的分类情况：试分别指出下述有限自动机的分类情况：FA2FA2+ab bc-

5、FA3FA3ab bc c-+ +c cc c+ +ab bc c-+ +c cb bFA5FA5结论：结论：DFADFA: FA2: FA2NFANFA: FA4,FA5: FA4,FA5FA1,FA3 (FA1,FA3 ( NFA)NFA)FA4FA4( NFA)( NFA) 有限自动机的有限自动机的等价变换等价变换, ,是指把是指把FA1FA1变换为变换为FA2,FA2,且且有有 L(FA1)=L(FA2)L(FA1)=L(FA2), ,主要包含以下两个内容：主要包含以下两个内容： 有限自动机的确定化有限自动机的确定化( NFA=DFA);( NFA=DFA);非确定机（非确定机（NFA

6、NFA）较易构造较易构造，但不好用！但不好用！ 确定机确定机 (DFA) (DFA) 较难构造，但好用！较难构造，但好用！ 任何一非确定机任何一非确定机NFA,NFA,皆可通过有效皆可通过有效算法把其化为等价的确定机算法把其化为等价的确定机DFADFA。 有限自动机的化简有限自动机的化简( ( 最小化最小化 ); ); 对任何一确定机对任何一确定机DFA1,DFA1,皆可通过有效算法把其化皆可通过有效算法把其化为等价的另一个确定机为等价的另一个确定机DFA2,DFA2,且且DFA2DFA2的状态最少。的状态最少。 对剩余的对剩余的 边，逆向逐一进行：边，逆向逐一进行：.消除消除 边算法边算法(

7、 ( NFANFA = = NFANFA 若存在若存在 闭路，闭路，则把则把 闭路上各节点闭路上各节点合而为一：合而为一：ab bc- ab bc- 标记标记隐含的隐含的开始态开始态和和结束态：结束态：开始态的开始态的 通路通路上的节点：上的节点：+ +结束态结束态逆向逆向 通路通路上节点：上节点：- - 删除一个删除一个 边；同时边；同时 引进引进新边新边 ：凡由原凡由原 边终点边终点发出的边，也要由其发出的边，也要由其始点始点发出。发出。 重复步骤，直到再无重复步骤，直到再无 边边为止。为止。+c cb b-b b + + +- -ab bc c 或或 DFADFA ): ): b bc

8、c a am m, ,a am mbcbcn n,a,am mc cn n|m0,n1 |m0,n1 L( )=L( )= NFANFA 标记标记隐含的隐含的开始态开始态和和结束态结束态：L(L( NFANFA)= ?)= ? 【例例3.93.9】考查考查 NFANFA ： +ab bc c- 闭路上的节点闭路上的节点等价等价（ ） 逆序逐一逆序逐一删除删除 边，边，同时同时引进引进新边：新边：+ + +，ab bc c-+ + -+ + NFANFA+ +ab bc c-+ +c c-+ + +ab bc c-+ + -+ + +, ,可可合而为一；合而为一；c c, ,_ _c c NFA

9、NFA NFANFA 按按 NFANFA (q qi i1 1, ,q qi in n ，a ak k)=q)=qj j1 1, ,q qj jn n 若若qqj j1 1, ,q qj jn n 未作为未作为状态行状态行标记，则作新行标记；标记，则作新行标记；a a1 1a a2 2a a3 3qq0 01 1, ,q q0 0n n 重复步骤，直到在再不出现新状态集为止；重复步骤，直到在再不出现新状态集为止； 标记标记DFADFA的的开始态开始态和和结束态结束态：第一行第一行qq0 01 1, ,q q0 0n n ，( (右侧右侧) )标记标记 + + ；凡是凡是状态行状态行中含有中含有

10、【注注】 必要时，新产生的必要时，新产生的DFADFA可用状态图表式。可用状态图表式。 NFANFA字母表中符号字母表中符号 开始态集开始态集 NFANFA 构造构造DFADFA的变换表的变换表( (框架框架) )： 的的结束状态结束状态者，者，( (右侧右侧) )标记标记 - - 。的变换函数的变换函数实施变换：实施变换： NFANFA+ab bc-+ab b-【例例3.103.10】联联合式自动机合式自动机NFA:NFA: 确定化过程确定化过程: :DFA:DFA:A AB BC CE EF FG GD D+ +- -a ac cb ba ab bc cc c- -b bb ba a- -

11、 -【注注】A,B,C,A,B,C, 状态集的代码状态集的代码 c cb b a aA1,4A1,4C2,4C2,4E5E5F2F2G4G4D3D3B2,5B2,5+ +- - - - -D3D3F2F2E5E5G4G4D3D3F2F2E5E5D3D3C2,4C2,4B2,5B2,5 有限自动机的有限自动机的最小化最小化, ,又称有限自动机的又称有限自动机的化简化简；是；是指：指： 对给定的确定机对给定的确定机DFA1,DFA1,构造另一个确定机构造另一个确定机DFA2,DFA2,使使得得 L(DFA1)=L(DFA2),L(DFA1)=L(DFA2),且且DFA2DFA2的状态最少。的状态最

12、少。 有限自动机最小化算法，是指构造满足下述条件有限自动机最小化算法，是指构造满足下述条件的确定有限自动机的确定有限自动机( (称为称为最小机最小机) )： 删除删除无用状态；无用状态； 【等价状态等价状态】是指这样的两个状态，若分别把其是指这样的两个状态，若分别把其看作看作开始态开始态，二者接受的符号串集合相同。，二者接受的符号串集合相同。 合并合并等价状态。等价状态。 【无用状态无用状态】是指由是指由开始态开始态达不到的状态达不到的状态( (不可不可达达) )或者由其出发不能到达或者由其出发不能到达结束态结束态的状态的状态( (不终结不终结) )。其中其中【例例3.133.13】+ab b

13、c- 【例例3.123.12】+ab bc-【注注】如何判断两个状态的等价性？梢后再讨论。如何判断两个状态的等价性？梢后再讨论。2 2 4 4 ？3 3 5 5 ？4 4 5 5 ？判断等价性：判断等价性：2 2 3 3 ？ 2,3 2,3节点构成节点构成 闭路闭路,2,32,3等价等价；可；可合而为一合而为一a-b ba a- a a【例例3.113.11】+ab bc-a ac cb b+ab bb b-c cb bd d不可达不可达不终结不终结【删除删除不可达不可达状态状态】 构造可达状态集构造可达状态集 Q QARAR 设设 q q0 0 为开始态，则为开始态，则 令令 q q0 0Q

14、QAR AR ； 若若 q qi iQQAR AR 且有且有 ( (q qi i,a)= ,a)= q qj j 则令则令 q qj jQQAR AR ； 重复执行，直到重复执行，直到Q QARAR不再增大为止。不再增大为止。 从状态集从状态集Q Q中，删除不在中，删除不在Q QARAR中的所有状态。中的所有状态。【删除删除不终结不终结状态状态】 构造可终结状态集构造可终结状态集 Q QFNFN 设设 q qi i 为结束态，则为结束态，则 令令 q qi iQQFN FN ； 若若 q qj jQQFN FN 且有且有 ( (q qi i,a)= ,a)= q qj j 则令则令 q qi

15、iQQFN FN ； 重复执行，直到重复执行，直到Q QFNFN不再增大为止。不再增大为止。 从状态集从状态集Q Q中，删除不在中，删除不在Q QFNFN中的所有状态。中的所有状态。 两个状态两个状态i,ji,j等价，当且仅当满足下面两个条件：等价，当且仅当满足下面两个条件： 必须必须同是同是结束态结束态，或，或同不是同不是结束态结束态； 对所有字母表上符号，状态对所有字母表上符号，状态i,ji,j必变换到等价状态。必变换到等价状态。【例例3.143.14】把下述自动机最小化：把下述自动机最小化： 初分成两个不等价子集：初分成两个不等价子集：Q Q1 1=1,2,Q=1,2,Q2 2=3=3

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

17、的子集，条件是： 同一同一Q Qi i中两个状态中两个状态i,j,i,j,若对字母表中的某若对字母表中的某个符号，变换到已划分的不同的状态集中，则个符号，变换到已划分的不同的状态集中，则i,ji,j应分离应分离: : 重复步骤，直到再不能划分为止；重复步骤，直到再不能划分为止； 合并最终划分的每个子集中的各状态合并最终划分的每个子集中的各状态( (合而为一合而为一) )。如如 (i,a)(i,a)QQm m , , (j,a)(j,a)QQn n 且且 mnmn - - 划分不等价状态集划分不等价状态集【例例3.153.15】 化简下述化简下述 DFA:DFA:. . 删除无用状态删除无用状态

18、( (不终结不终结) )： 动态构造动态构造DFADFA变换表变换表，即从开始状态，即从开始状态 1 1 出发，出发，把变换后的状态填入表项，并同时作为新行标记；把变换后的状态填入表项，并同时作为新行标记；【注注】 DFA DFA 中的状态中的状态 2 2，8 8 被删除被删除! ! + +- - - -b ba ab ba ab ba ab ba ab ba aa aa ab ba aDFADFA的变换表：的变换表：如此下去，直到再不出现新状态为止。未出现的状如此下去，直到再不出现新状态为止。未出现的状态，就是无用的状态。态，就是无用的状态。b ba a4 46 64 47 73 37 75

19、 56 64 44 45 51 13 33 36 61 1+ +- - - - (1,a)=6 ,(1,a)=6 , (3,4,a)=1,4 (3,4,a)=1,4 划分成划分成 Q Q1 1=1, Q=1, Q2 2=3,4=3,4； 4 46 64 47 73 37 75 56 64 44 45 51 13 33 36 61 1b ba a+ +- - - -DFA:DFA:. . 合并等价状态合并等价状态: : 令令 Q QNENE= 1,3,4, 5,6,7 = 1,3,4, 5,6,7 取取 1,3,4 1,3,4 ：即即 Q QNENE= 1,3,4, 5,6,7 = 1,3,4,

20、 5,6,7 取取 3,43,4： (3,a)=1 ,(3,a)=1 , (4,a)=4(4,a)=4 划分划分 Q Q1 1=3, Q=3, Q2 2=4 =4 即即 Q QNENE= 1,3,4, 5,6,7 = 1,3,4, 5,6,7 取取 5,6,7: 5,6,7: 同理，可划分成同理，可划分成 Q Q1 1=5, Q=5, Q2 2=6,7=6,7； 最后：最后： Q QNENE= 1,3,4, 5,6,7 = 1,3,4, 5,6,7 不等价集不等价集4 46 64 47 73 37 75 56 64 44 45 51 13 33 36 61 1b ba a+ +- - - -DFA:DFA:合并等价状态：合并