《第3章 有穷自动机精选文档.ppt》由会员分享，可在线阅读，更多相关《第3章 有穷自动机精选文档.ppt（74页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第3章章 有穷自动机有穷自动机本讲稿第一页，共七十四页有穷自动机 有穷自动机有穷自动机(也称有限自动机也称有限自动机)作为一种识别装置，它作为一种识别装置，它能准确地识别能准确地识别正规集正规集，即识别，即识别正规文法正规文法所定义的语言所定义的语言和和正规式正规式所表示的集合，引入有穷自动机这个理论，所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工正是为词法分析程序的自动构造寻找特殊的方法和工具。具。有穷自动机分为两类：确定的有穷自动机有穷自动机分为两类：确定的有穷自动机(Deterministic Finite State Automata)和不确定和
2、不确定的有穷自动机的有穷自动机(NonDeterministic Finite State Automata)。本讲稿第二页，共七十四页FSA例例3.1 :识别一个由带符号或无符号十进制数组成的语言。识别一个由带符号或无符号十进制数组成的语言。开始状态终止状态本讲稿第三页，共七十四页有穷自动机有穷自动机有穷自动机有穷自动机DFSADFSA定义定义定义定义3.13.1：一个确定的有穷自动机（一个确定的有穷自动机（DFSA）M是一个五元组：是一个五元组：M=（Q，t，q0，F）其中其中1 1 Q是一个有穷集，它是一个有穷集，它的每个元素的每个元素的每个元素的每个元素称称为为为为一个一个状态状态状态
3、状态；2 2 是是是是一个有穷字母表，它的每个元素称为一个输入符号，一个有穷字母表，它的每个元素称为一个输入符号，所以也称所以也称为为输入符号字母表输入符号字母表输入符号字母表输入符号字母表；3 3 t t t t是转换函数是转换函数是转换函数是转换函数，是在，是在QQ上的映射，即，如上的映射，即，如:t=(:t=(q，x）=q，（，（q，q Q）就意味着，当前状态为就意味着，当前状态为q q，输入符为输入符为x x时，时，将转换为下一个状态将转换为下一个状态q，我们把我们把q称作称作q q的一个后继状态；的一个后继状态；4 q0 Q Q是唯一是唯一是唯一是唯一的一个的一个开始状态开始状态开始
4、状态开始状态；5 5 F F F F Q是是是是一个一个终止状态集终止状态集终止状态集终止状态集，它至少由一个终止状态组成。，它至少由一个终止状态组成。本讲稿第四页，共七十四页状态转换表状态转换表例3.1状态转换表本讲稿第五页，共七十四页DFSA 例例3.2DFA A=（q0,q1,q2,q3,a,b,t,q0,q0）其其中中 t 定义为：定义为：t（q0，a）=q1 t（q2，a）=q3t（q0，b）=q3 t（q2，b）=q1t（q1，a）=q0t（q3，a）=q2t（q1，b）=q2 t（q3，b）=q0本讲稿第六页，共七十四页状态转换表状态转换表t（q0，a）=q1 t（q2，a）=q
5、3t（q0，b）=q3 t（q2，b）=q1t（q1，a）=q0t（q3，a）=q2t（q1，b）=q2 t（q3，b）=q0字符状态本讲稿第七页，共七十四页DFSA 的状态图表示的状态图表示t（q0，a）=q1 t（q2，a）=q3t（q0，b）=q3 t（q2，b）=q1t（q1，a）=q0t（q3，a）=q2t（q1，b）=q2 t（q3，b）=q0bq2q1q3q0aaabbab本讲稿第八页，共七十四页DFSA 例3.3：DFSA M=(0，1，2，3，a，b，f，0，3)，其中：f定义如下：f(0，a)=1f(0，b)=2f(1，a)=3 f(1，b)=2f(2，a)=1f(2，b)
6、=3f(3，a)=3 f(3，b)=3状态转换矩阵状态转换矩阵0312aaaa状态转换图状态转换图bbbb本讲稿第九页，共七十四页构型和移动构型和移动 对于给定的输入串，假定对于给定的输入串，假定DFSA已经完成了若干次移动，为了预已经完成了若干次移动，为了预测它的进一步行为，只需要知道测它的进一步行为，只需要知道“当前状态当前状态”和和“尚待扫描输入串尚待扫描输入串”。对它的描述称为对它的描述称为构型构型，记为，记为(q,),其中其中q是一个状态，是一个状态，是尚待输入是尚待输入的符号串。的符号串。(q0,)-初始构型初始构型(q,)-终止构型终止构型(q,a)(q,)其中其中a,*用用符号
7、表示自动机的移动，即从一种构型到另一种构型的符号表示自动机的移动，即从一种构型到另一种构型的转换转换DFSA的工作过程就是进行一系列的移动的过程。的工作过程就是进行一系列的移动的过程。*表示表示0次移动或多次移动。次移动或多次移动。+表示表示？DFSA 所识别的语言所识别的语言L(M):L(M)=*|(q0,)*(q,)qF 本讲稿第十页，共七十四页DFSA=(Q,DFSA=(Q,t,q0,F),),扩充的映射扩充的映射扩充的映射扩充的映射t:t:Q*Q定义为：定义为：定义为：定义为：（1 1）t（q，）=q （2 2）t t（q q，a a）=t=t（t t（q q，a a），），），），）
8、其中其中qQ，a，*DFSA=(Q,DFSA=(Q,t,q0,F)，如果如果如果如果t（q0，）=q=qF,则符号串则符号串 可可可可被有穷自动机被有穷自动机被有穷自动机被有穷自动机DFSADFSA所接受。所接受。有穷自动机有穷自动机有穷自动机有穷自动机DFSADFSA所接受的符号串集，记为所接受的符号串集，记为所接受的符号串集，记为所接受的符号串集，记为L(M).L(M).DFSA 可接受的符号串可接受的符号串本讲稿第十一页，共七十四页例例3 3.2中的有穷自动机中的有穷自动机A，t(q0,aabb)=t(t(q0,a),abb)=t(q1,abb)=t(t(q1,a),bb)=t(q0,b
9、b)=t(t(q0,b),b)=t(q3,b)=q0 F。所以符号串所以符号串aabb能被有穷自动机能被有穷自动机A所接受。所接受。t（q0，a）=q1 t（q2，a）=q3t（q0，b）=q3 t（q2，b）=q1t（q1，a）=q0t（q3，a）=q2t（q1，b）=q2 t（q3，b）=q0bq2q1q3q0aaabbab本讲稿第十二页，共七十四页自动机的等价自动机的等价定义定义3.2 给定两个有穷自动机给定两个有穷自动机M和和M，如果如果L(M)=L(M)，则称自则称自动机动机M和和M等价。等价。例例3.DFSA M=(q0,q1,a,b,t,q0,q0),其中其中t(q0,a)=q1
10、,t(q1,b)=q0.DFSA M=(q0,q1,q2,a,b,t,q0,q2),其中其中t(q0,a)=q1,t(q1,b)=q2,t(q2,a)=q1.则则L(M)=L(M)=(ab)n|n 1,所以自动机所以自动机M,M等价。等价。本讲稿第十三页，共七十四页非确定的有穷自动机非确定的有穷自动机NDFSA定义定义3.一个非确定的有穷自动机是一个五元组，一个非确定的有穷自动机是一个五元组，NDFA=Q，t，Q0，F，其中其中QQ为状态为状态为状态为状态的有穷非空的有穷非空集集集集，为为为为有穷输入有穷输入字母表字母表字母表字母表，t t为为为为Q 到到Q的子集的子集(多值映射多值映射多值映
11、射多值映射)，QQ0 0 Q是初始状态是初始状态集集集集，F F Q为终止状态集为终止状态集为终止状态集为终止状态集。一个确定的有穷自动机（一个确定的有穷自动机（DFSA）M是一个五元组：是一个五元组：M=（Q，t，q0，F）其中其中1 1 Q是一个有穷集，它是一个有穷集，它的每个元素的每个元素的每个元素的每个元素称称为为为为一个一个状态状态状态状态；2 2 是是是是一个有穷字母表，它的每个元素称为一个输入符号，所以也称一个有穷字母表，它的每个元素称为一个输入符号，所以也称为为输入符号字母表输入符号字母表输入符号字母表输入符号字母表；3 3 t t t t是转换函数是转换函数是转换函数是转换函
12、数，是在，是在QQ上的映射，即，如上的映射，即，如:t=(:t=(q，x）=q，（，（q，q Q）就意味着，当前状态为就意味着，当前状态为q q，输入符为输入符为x x时，将转换为下一个状态时，将转换为下一个状态q，我们把我们把q称作称作q q的一的一个后继状态；个后继状态；4 q0 Q Q是唯一是唯一是唯一是唯一的一个的一个开始状态开始状态开始状态开始状态；5 5 F F F F Q是是是是一个一个终止状态集终止状态集终止状态集终止状态集，它至少由一个终止状态组成。，它至少由一个终止状态组成。本讲稿第十四页，共七十四页例子例子NDFSA N=（S，P，Z，0，1，t，S，P，Z）其中其中 t
13、（S，0）=Pt（S，1）=S，Zt（P，1）=Zt（Z，0）=Pt（Z，1）=PSPZ00,1111N状态图表示状态图表示本讲稿第十五页，共七十四页例子例子3.6NDFSA=（Q，t，Q0，F）其中其中 Q=q0,q1,q2,q3,=x,y,Q0=q0,F=q1.t（q0，x）=q1,q2,t（q0，y）=q0,t（q1，x）=q0,t（q1，y）=q1,q2 t（q2，x）=q3,t（q2，y）=q3 t（q3，x）=q1,q3,t（q3，y）=q3NDFA状态图表示状态图表示q0yx,yyxq1q3q2xxxyx,y本讲稿第十六页，共七十四页NDFSA与与DFSA的区别的区别NDFSA有
14、一个开始状态集合，而有一个开始状态集合，而DFA只有一个开始状态；只有一个开始状态；NDFSA的映射是的映射是Q Q的子集，是一个多值的子集，是一个多值映映射，而射，而DFSA是是Q Q的一个单值的一个单值映射。映射。本讲稿第十七页，共七十四页例例3.7 证明符号串证明符号串xyx能被例能被例3.6中的中的NDFSA，所所接受。接受。证明：因为证明：因为t(q0,xyx)=t(q1,yx)t(q2,yx)(t(q0,x)=q1,q2)=t(q1,x)t(q2,x)t(q3,x)(t(q1,y)=q1,q2,t(q2,y)=q3)=q0 q3 q3 q1,q3=q0,q1,q3 q1,q3=q0
15、,q1,q3q1 t(q0,xyx)=q0,q1,q3,q1 F所以所以xyx能被该能被该NDFSA所接受。所接受。本讲稿第十八页，共七十四页空移环路的寻找空移环路的寻找如果自动机的弧上允许标记如果自动机的弧上允许标记，则称此自动，则称此自动机为机为 自动机，记为自动机，记为 NDFSA或或 DFSA.q1q2 q1q2 q3 q1q2q3 qn(a)(b)(c)本讲稿第十九页，共七十四页空移环路的消除空移环路的消除找到空移环路之后，要消除它只要把空移环路上所找到空移环路之后，要消除它只要把空移环路上所有结点有结点q1,q2,qn合成一个结点，并消除它们所有合成一个结点，并消除它们所有的的 弧
16、。如果其中的某一个结点弧。如果其中的某一个结点qi(i=1或或2,n)是开始结是开始结点或终止结点，则将此合并后的新结点相应地设置为开点或终止结点，则将此合并后的新结点相应地设置为开始状态或终止状态。始状态或终止状态。q0q1 q2aq3q4 abbbq0q2aq3bbba(1)(2)例例3.8本讲稿第二十页，共七十四页确定化确定化-子集法子集法(自学自学)给定一个给定一个NDFSA A=(Q,Q,t,Q0,F)是一个非确定的有穷自动机，是一个非确定的有穷自动机，一定可以构造一个和它等价的确定有穷自动机一定可以构造一个和它等价的确定有穷自动机DFSA A=(Q,Q,t,q0,F)，即即L(A)
17、=L(A)。构造步骤构造步骤：(1)A与与 A的字母表的字母表完全相同；完全相同；(2)把把A的每一个的每一个状态子集状态子集作为作为A的一个状态；的一个状态；(3)对对A的任意状态子集的任意状态子集r1,r2,rn，riQ(i=1,2,n)，令令r=r1,r2,rn,rQ.A的映射定义为的映射定义为：t(r,a)=qQ,其中其中a,q=q1,q2,qm,而而q1,q2,qm=t(r1,a)t(r2,a)t(rn,a);(4)A的的开始状态开始状态q0=s1,s2,sk，其中其中si Q0(i=1,2,k);(5)A的的终止状态终止状态F=e|e=e1,e2,ep,e1,e2,ep F .本讲
18、稿第二十一页，共七十四页例例3.10NDFA=（Q，t，Q0，F）其中其中 Q=q0,q1,q2,q3,=x,y,Q0=q0,F=q1.t（q0，x）=q1,q2,t（q0，y）=q0,t（q1，x）=q0,t（q1，y）=q1,q2,t（q2，x）=q3,t（q2，y）=q3,t（q3，x）=q1,q3,t（q3，y）=q3DFA=(Q,t,q0,F).(1)=x,y;(2)Q=q0,q1,q2,q3,q0,q1,q0,q2,q0,q3,q1,q2,q1,q3,q2,q3,q0,q1,q2,q0,q1,q3,q0,q2,q3,q1,q2,q3,q0,q1,q2,q3(3)定义映射定义映射t:
19、t(q0,x)=q1,q2,t(q0,y)=q0,t(q1,x)=q0,t(q1,y)=q1,q2,t(q2,x)=q3,t(q2,y)=q3,t(q3,x)=q1,q3,t(q3,y)=q3,t(q0,q1,x)=q0,q1,q2,t(q0,q1,y)=q0,q1,q2,.t(q0,q1,q2,q3,x)=q0,q1,q2,q3,t(q0,q1,q2,q3,y)=q0,q1,q2,q3.(4)DFA的开始状态的开始状态q0=q0(5)DFA的开始状态集合的开始状态集合F=q1,q0,q1,q2,q1,q3,q1,q0,q1,q2,q0,q1,q3,q1,q2,q3,q1,q2,q3,q4本讲
20、稿第二十二页，共七十四页确定化确定化-造表法造表法 子集法的确定，如果状态数子集法的确定，如果状态数n很大，确定化后的状很大，确定化后的状态数将更大态数将更大2n-1，并且其中很多是不可到达的状态而造并且其中很多是不可到达的状态而造表法，更加简单而有效。表法，更加简单而有效。步骤：步骤：确定确定DFSA的的开始状态开始状态，从开始状态开始分别计算对，从开始状态开始分别计算对不同输入字母的映象，如果产生新的状态，则继续不同输入字母的映象，如果产生新的状态，则继续计算新状态的映象，重复这个过程一直到没有新的计算新状态的映象，重复这个过程一直到没有新的状态出现为止。状态出现为止。本讲稿第二十三页，共
21、七十四页造表法确定化造表法确定化 输入输入状态状态xyq0 q0q1,q2 q1q0 q0q1,q2 q1q0,q3 q2q1,q2,q3 q3 q0,q3 q2q1,q2,q3 q3 q0,q3 q2q1,q2,q3 q3 q0,q1,q3 q4q1,q2,q3 q3 q0,q1,q3 q4q0,q1,q2,q3 q5q0,q1,q2,q3 q5q0,q1,q2,q3q5q0,q1,q2,q3 q5q0,q1,q2,q3 q5本讲稿第二十四页，共七十四页确定化后的状态转换图确定化后的状态转换图q0q2xq4xxyyxyq3q1q5yx,yx,y本讲稿第二十五页，共七十四页 NDFA的确定化的
22、确定化-闭包、弧转换闭包、弧转换：对于状态集合：对于状态集合I，可以定义以下两种运算，可以定义以下两种运算-closure(I)：称为状态集合：称为状态集合I的的-闭包，其中：闭包，其中：如果如果sI，则有，则有s-closure(I)；如果如果sI，s是从是从s出发经过任意条出发经过任意条弧能弧能 够到够到 达的状态，则有达的状态，则有s-closure(I)。move(I,a)：称为状态集合称为状态集合I的的a弧转换。该集合是从弧转换。该集合是从I中的某一中的某一 状态出发经过一条状态出发经过一条a弧到达的状态结的全体。弧到达的状态结的全体。设设I=s1,s2,.,sn，则有，则有 mov
23、e(I,a)=f(s1,a)f(s2,a).f(sn,a)。NDFA的确定化包含去掉空移、和空环路及确定化的功能。的确定化包含去掉空移、和空环路及确定化的功能。本讲稿第二十六页，共七十四页例例:-closure(0)-closure(1,3)move(2,7,9,a)=0,1,2,4,7=1,2,3,4,6,7=3,8本讲稿第二十七页，共七十四页NDFSA到到DFSA的转换：的转换：对于每个对于每个NFSA N=(KN,N,fN,SN,ZN)，存在一，存在一个个DFSA M=(KM,M,fM,SM,ZM)，使得，使得L(M)=L(N)。具体转换步骤如下：。具体转换步骤如下：1)令令M=N；2)
24、设设N=a1,a2,.,an，则构造一个含有，则构造一个含有n+1列的表格，其中第列的表格，其中第1列标记列标记为状态为状态T，第，第2n+1列分别标记为列分别标记为fM(T,a1),.,fM(T,an)。其中。其中fM(T,ai)=-closure(move(T,ai)；3)置该表的第置该表的第1行第行第1列为列为T0=-closure(SN)；4)根据第根据第1列分别计算同一行其他各列的值。如果该值未曾出现在第列分别计算同一行其他各列的值。如果该值未曾出现在第1列，列，则把它命名为则把它命名为Ti并填入到下面空行的第并填入到下面空行的第1列位置上；列位置上；5)重复第重复第4步，直至某行第
25、步，直至某行第2n+1列的所有元素全都出现在第列的所有元素全都出现在第1列上为列上为止；止；6)令令SM=第第1行第行第1列元素列元素T0；7)如果如果Ti含有含有ZN的元素，则令的元素，则令Ti ZM。本讲稿第二十八页，共七十四页2 while（C中存在尚未被标记的子集中存在尚未被标记的子集T）do 标记标记T；for 每个输入字母每个输入字母a do U:=-closure(move(T,a)；if U不在不在C中中 then 将将U作为未标记的子集加在作为未标记的子集加在C中中 假定所构造的子集族为假定所构造的子集族为C，即，即C=(T1,T2,.TI),其中其中T1,T2,.TI为状态
26、为状态K的子集。的子集。1 开始，令开始，令-closure(K0)为为C中唯一成员，并且它中唯一成员，并且它是未被标记的。是未被标记的。本讲稿第二十九页，共七十四页例例3.6S521346H abba bb aa例：把下面的例：把下面的NDFSA N转换为等价的转换为等价的DFSA M 本讲稿第三十页，共七十四页T Tf fM M(T,a)(T,a)f fM M(T,b)(T,b)T T0 0=S,5,1=S,5,1T T1 1=5,3,1=5,3,1T T2 2=5,4,1=5,4,1T T1 1=5,3,1=5,3,1T T3 3=5,3,1,2,6,H=5,3,1,2,6,HT T2
27、2T T2 2=5,4,1=5,4,1T T1 1T T4 4=5,4,1,2,6,H=5,4,1,2,6,HT T3 3=5,3,1,2,6,H=5,3,1,2,6,HT T3 3T T5 5=5,4,1,6,H=5,4,1,6,HT T4 4=5,4,1,2,6,H=5,4,1,2,6,HT T6 6=5,3,1,6,y=5,3,1,6,yT T4 4T T5 5=5,4,1,6,H=5,4,1,6,HT T6 6T T4 4T T6 6=5,3,1,6,H=5,3,1,6,HT T3 3T T5 5例中对应的状态转换表例中对应的状态转换表本讲稿第三十一页，共七十四页例中对应的状态转换图例
28、中对应的状态转换图本讲稿第三十二页，共七十四页例：把下面的例：把下面的NDFSA N=转换为等价的转换为等价的DFSA M 本讲稿第三十三页，共七十四页本讲稿第三十四页，共七十四页消除不可达状态消除不可达状态在自动机中，从开始状态没有一条路径能在自动机中，从开始状态没有一条路径能达到的状态称为达到的状态称为不可达状态不可达状态。不可达状态。不可达状态对于生成自动机的语言毫无意义，因此，对于生成自动机的语言毫无意义，因此，应从自动机中消除。应从自动机中消除。DFSA的化简的化简本讲稿第三十五页，共七十四页01S0S1S50S1S2S71S2S2S51S3S5S70S4S5S60S5S3S10S6
29、S8S01S7S0S11S8S3S6001S0S1S50S1S2S71S2S2S51S3S5S70S5S3S10S7S0S11化简后的结果：左右等价DFSA的化简的化简本讲稿第三十六页，共七十四页DFSA的化简的化简对对DFSA化简就是使它的状态数最少，即对任意一个确定的化简就是使它的状态数最少，即对任意一个确定的有穷自动机有穷自动机A，要构造另一个确定的有穷自动机要构造另一个确定的有穷自动机A，使使L(A)=L(A)，且且A的状态个数不超过的状态个数不超过A的状态个数。的状态个数。状态等价：状态等价：如果从状态如果从状态q1出发能扫描任意串出发能扫描任意串w而停止于终态，而停止于终态，那么从
30、状态那么从状态q2出发也能扫描同一个串出发也能扫描同一个串w而停止于终态。则而停止于终态。则DFSA的的两个两个状态状态q1与与q2是等价的是等价的。若。若DFSA的两个状态的两个状态q1与与q2不等价，不等价，则称状态则称状态q1与与q2是是可区分的可区分的。若若q1,q2为为DFSA中的两个状态，若中的两个状态，若 (q1,w)*(s1,),(q2,w)*(t1,)其中其中 w*，且且s1与与t1都为终止状态都为终止状态则则q1,q2等价。等价。本讲稿第三十七页，共七十四页DFSA化简的化简的基本思想基本思想是将状态集分解成若干互不相交的子集，是将状态集分解成若干互不相交的子集，使每个子集
31、的状态都是等价的，而不同子集的状态是不等价的使每个子集的状态都是等价的，而不同子集的状态是不等价的即是可区分的。即是可区分的。化简步骤化简步骤(1)将状态集合分解为两个子集合，所有终止状态为一个子集，其他将状态集合分解为两个子集合，所有终止状态为一个子集，其他非终止状态为一个子集。非终止状态为一个子集。(2)对每个子集再进行分解，分解后的两个状态对每个子集再进行分解，分解后的两个状态 同于一个，同于一个，当且仅当且仅当对当对任何任何一个输入字母，它们的映象属于同一个子集。一个输入字母，它们的映象属于同一个子集。(3)重复（重复（2）一直到不能再分解为止。）一直到不能再分解为止。本讲稿第三十八页
32、，共七十四页如图，状态如图，状态0和和4是可区别的。是可区别的。状态状态2和和3是可区别的，因为读入是可区别的，因为读入b后分别到达后分别到达2和和4，而，而2和和4不不是等价的。是等价的。b02134abaaaabbbDFA M本讲稿第三十九页，共七十四页DFSA的化简的化简(书书P62)本讲稿第四十页，共七十四页1643257aaaaaaabbbbbbb本讲稿第四十一页，共七十四页 将将M分成两个子集：分成两个子集：一个终态（可接受态）组成，一个非终态组成。一个终态（可接受态）组成，一个非终态组成。P0(1,2,3,4,5,6,7)第第1个子集个子集1,2,3,4中：中：1,2中的状态和中
33、的状态和3,4中的任何状态在读入中的任何状态在读入a后到达了不等后到达了不等价的状态，两个状态都是不可区别的。价的状态，两个状态都是不可区别的。P1(1,2,3,4,5,6,7)P1中的中的3,4对应输入符号对应输入符号a或或b，将再分割：，将再分割：P2(1,2,3,4,5,6,7)P2中的中的5,6,7可有输入符号可有输入符号a或或b，分割为：，分割为：本讲稿第四十二页，共七十四页1643257aaaaaaabbbbbbbP3(1,2,3,4,5,6,7)1,2,6,7不能再分割，也即等价的。16435aaaaabbbbb本讲稿第四十三页，共七十四页书书P64例例 q0q2xq4xxyyx
34、yq3q1q5yx,yx,y先将终止状态归为一个子集先将终止状态归为一个子集S1=q1,q3,q4,q5，其余非终止状态归为另一其余非终止状态归为另一个子集个子集S2=q0,q2。因为因为t(q1,x)=q2 S2,t(q3,x)=q4,t(q4,x)=q5，t(q5,x)=q5 S1，所以将所以将S1分解为两个子集分解为两个子集S1=q1,S2=q3,q4,q5。因为因为t(q0,x)=q1 S1,t(q2,x)=q3 S2,所以将所以将S2分解成分解成q0 q2q0q2xyxyq1q3yx,yx本讲稿第四十四页，共七十四页从从DFA到程序表示到程序表示如果对如果对DFA的每个状态都事先指明
35、它所要完成的任务，的每个状态都事先指明它所要完成的任务，再把从状态发出的弧上所标记的输入字母作看作控再把从状态发出的弧上所标记的输入字母作看作控制条件，那么，制条件，那么，DFA实际上是一个程序流程图。实际上是一个程序流程图。q0q1q2l,dl非非l,d标识符DFAchar ch,namekname=read(ch)name=name+chread(ch)用name查找符号表，若没有，则填表，否则返回其地址q0q1q2ch=lch=l or d非l,d标识符程序流程图本讲稿第四十五页，共七十四页课堂练习课堂练习:将下面将下面NDFSA状态转换图，转换为状态转换图，转换为DFSA状态转换状态转
36、换图，并化简。图，并化简。SBZ00,1A C1本讲稿第四十六页，共七十四页本讲稿第四十七页，共七十四页从正规文法到从正规文法到FSA(自动机自动机)对于正规文法对于正规文法G可以直接构造一个有穷自动机可以直接构造一个有穷自动机A，使使L（A）=L（G）。）。构造步骤：构造步骤：(1)正规文法正规文法G中终结符号集作为中终结符号集作为A的字母输入表；的字母输入表；(2)文法文法G的每个非终结符号都作为的每个非终结符号都作为A的一个状态，文法的的一个状态，文法的开始符号作为开始符号作为A的开始状态；的开始状态；(3)在自动机在自动机A中增加一个新状态中增加一个新状态z作为自动机的终止状作为自动机
37、的终止状态；态；(4)对文法对文法G中形如中形如UaV(a VT或或a=,V VN)的产生的产生式，在自动机式，在自动机A中构造形如中构造形如t(U,a)=V的映射；的映射；(5)对文法对文法G中形如中形如Ua(a VT)的产生式，在自动机的产生式，在自动机A中中构造形如构造形如t(U,a)=z的映射；的映射；本讲稿第四十八页，共七十四页例：例：设正规文法设正规文法G19S：SaS|aA|bB,AbA|cC,BaB|dD,CcC|c,DdD|d由文法由文法G19构造的构造的FSA：SZDBCAaabbcadccdd本讲稿第四十九页，共七十四页例：设例：设GS=SaA,SbB,S,AaB,AbA
38、,BaS,BbA,B，则相应的，则相应的NFSA如下：如下：本讲稿第五十页，共七十四页从从DFSA到正规文法到正规文法构造步骤：构造步骤：(1)自动机的每个状态标记均作为正规文法的非终结自动机的每个状态标记均作为正规文法的非终结符，其中自动机开始符号的标记作为文法的开始符符，其中自动机开始符号的标记作为文法的开始符号。自动机的输入字母表中的所有符号作为正规文号。自动机的输入字母表中的所有符号作为正规文法的终结符；法的终结符；(2)对于自动机的映射对于自动机的映射t(U,a)=V（其中其中U,V是自动机的是自动机的状态标记，状态标记，a为输入符号），构造文法的一条产生为输入符号），构造文法的一条
39、产生式式UaV,U,V非终结符，非终结符，a终结符；终结符；(3)对于自动机的终止状态对于自动机的终止状态Z，在正规文法中增加一条在正规文法中增加一条产生式：产生式：Z 。本讲稿第五十一页，共七十四页例例3.11构造的正规文法构造的正规文法G21S：SxA|yBAyA|yC|xBBxC|yC|yA|C CASyx,yyByxxy本讲稿第五十二页，共七十四页正规表达式的定义正规表达式的定义定义定义3.9 字母表字母表上的正规表达式和正规集递归定义如下：上的正规表达式和正规集递归定义如下：(1)a ,a是是上的一个正规表达式，它所表示的正规集为上的一个正规表达式，它所表示的正规集为a;(2)空串空
40、串 是是上的一个正规表达式上的一个正规表达式,它所表示的正规集为它所表示的正规集为;(3)空集空集是是上的一个正规表达式上的一个正规表达式,它所表示的正规集为它所表示的正规集为;(4)设设e1,e2都是都是上的正规表达式，它们表示的正规集分别为上的正规表达式，它们表示的正规集分别为L(e1)和和L(e2)，则：则：i)e1|e2也是正规表达式，它所表示的正规集为也是正规表达式，它所表示的正规集为L(e1|e2)=L(e1)L(e2);ii)e1.e2也是正规表达式，它所表示的正规集为也是正规表达式，它所表示的正规集为L(e1.e2)=L(e1)L(e2);ii)(e1)*也是正规表达式，它所表
41、示的正规集为也是正规表达式，它所表示的正规集为L(e1)*)=(L(e1)*.本讲稿第五十三页，共七十四页正规表达式的性质正规表达式的性质定义定义3.10 设设e1,e2是是上的正规表达式，若上的正规表达式，若L(e1)=L(e2)，则则e1与与e2等价，记为等价，记为e1=e2.如如a|(ba)*=(ba)*|a.定理定理3.1设设e1,e2是是上的正规表达式，则上的正规表达式，则(1)e1|e2=e2|e1;(2)(e1e2)e3=e1(e2e3),(e1|e2)|e3=e1|(e2|e3);(3)e1(e2|e3)=e1e2|e1e3,(e1|e2)e3=e1e3|e2e3;(4)e1=
42、e1 =e1本讲稿第五十四页，共七十四页正规式正规集aaa|ba,b (ab)abab (a.b)(a|b)a,b(a|b)(a|b)aa,ab,ba,bba*,a,aa,.(a|b)*,a,b,.,所有由a和b组成的串ba*所有以b为首后跟任意多个a的串a(a|b)*上所有以a为首的串例：例：令=a,b，则有：本讲稿第五十五页，共七十四页正规式和有穷自动机的等价性正规式和有穷自动机的等价性1.对于对于上的上的NDFSA M，可以构造一个，可以构造一个上的正规式上的正规式e,e,使得使得L(e)=L(M)。2.2.对于对于上的一个正规式上的一个正规式e，可以构造一个，可以构造一个上的上的NDF
43、SA M，使得，使得L(M)=L(e)。本讲稿第五十六页，共七十四页正规表达式到正规表达式到NDFSA的转换的转换步骤步骤:(1)先构造一个广义的先构造一个广义的NDFA转换图，只有转换图，只有S，Z两个状态，两个状态，S是开始状态，是开始状态，Z是终止状态，弧上是正规表达式是终止状态，弧上是正规表达式e;(2)按照下按照下面替换规则，对面替换规则，对e进行分解，直到转换图中所有弧上都是进行分解，直到转换图中所有弧上都是的单的单个符号或个符号或 为止。为止。ACBe1e2ABe1 e2ABe1e2ABe1|e2ACB e1ABe1*(1)(2)(3)替换规则本讲稿第五十七页，共七十四页例例3.
44、15设设=x,y,x,y,上的正规表达式上的正规表达式e=e=xyxy*(xy|yx)x(xy|yx)x*，构造一个构造一个NDFA MNDFA M，使使L(M)=L(e).L(M)=L(e).xyxy*(xy|yx)x(xy|yx)x*SZx x(xy|yx)(xy|yx)SZ136y y*x x*Zx xyS236x x xyxy1 7 yxyx5SZ236x x y yx x1 y7 x x4y yx x本讲稿第五十八页，共七十四页NDFSA到正规表达式的转换到正规表达式的转换步骤步骤:(1)在在NDFSA中新设置一中新设置一个唯一的开始状态个唯一的开始状态S和唯一的和唯一的终止状态终止
45、状态Z；(2)从开始状态从开始状态S到原来的到原来的开始状态连接开始状态连接 弧，再从原来弧，再从原来的终止状态到的终止状态到Z状态也连接状态也连接 弧；弧；(3)按照替换规则进行按照替换规则进行替换，直到状态图中只剩下替换，直到状态图中只剩下S和和Z，在在S，Z弧上的表达式弧上的表达式就是所求的结果。就是所求的结果。本讲稿第五十九页，共七十四页本讲稿第六十页，共七十四页从正规文法与正规表达式从正规文法与正规表达式产生式产生式正规式正规式规则规则1 1AxBAxB、ByByA=xyA=xy规则规则2 2AxA|yAxA|yA=xA=x*y y规则规则3 3AxAx、AyAyA=x|yA=x|y
46、正规文法正规文法G=(VN,VT,P,S)到正规式到正规式r的转换：的转换：利用以下转换规则利用以下转换规则生成产生式，最后只剩下一个产生式，该产生式的左部为文生成产生式，最后只剩下一个产生式，该产生式的左部为文法的开始符号法的开始符号S，右部不含非终结符号。，右部不含非终结符号。一个语言可以由正规文法定义，也可以由正规式定义。对一个语言可以由正规文法定义，也可以由正规式定义。对任何一个正规文法，存在一个定义同一个语言的正规式；任何一个正规文法，存在一个定义同一个语言的正规式；反之，对每个正规式，存在一个生成同一个语言的正规文反之，对每个正规式，存在一个生成同一个语言的正规文法。法。本讲稿第六
47、十一页，共七十四页例：正规文法例：正规文法GS：SaA、Sa、AaA、AbA、Aa、Ab转换为正规式。转换为正规式。S=a|aA；A=(aA|bA)|(a|b)=(a|b)A|(a|b)=(a|b)*(a|b)；S=a|a(a|b)*(a|b)=a(|(a|b)*(a|b)=a(a|b)*。本讲稿第六十二页，共七十四页正规式正规式r到正规文法到正规文法G=(VN,VT,P,S)的转换：的转换：具体转换步骤如下。具体转换步骤如下。1)令令VT=；2)令令S为为G的开始符号，的开始符号，VN=S，生成产生式，生成产生式Sr；3)如果如果x、y是正规式，则对形如是正规式，则对形如Axy的产生式，重写
48、为的产生式，重写为AxB和和By两个产生式，并把两个产生式，并把B加到加到VN；4)如果如果x、y是正规式，则对形如是正规式，则对形如Ax*y的产生式，重写为的产生式，重写为AxA、Ay两个产生式；两个产生式；5)如果如果x、y是正规式，则对形如是正规式，则对形如Ax|y的产生式，重写为的产生式，重写为Ax和和Ay两个产生式；两个产生式；6)重复步骤重复步骤35，直到，直到G中的每个产生式的右部最多含有一个非终结中的每个产生式的右部最多含有一个非终结符为止。符为止。本讲稿第六十三页，共七十四页例：设例：设=a,b，把正规式，把正规式r=a(a|b)*转换为等价的正规文法转换为等价的正规文法G=
49、(VN,VT,P,S)。1)令令VT=a,b；2)令令S为为G的开始符号，的开始符号，VN=S，生成产生式，生成产生式Sa(a|b)*；3)产生式产生式Sa(a|b)*重写为重写为SaA和产生式和产生式A(a|b)*，VN=S,A；4)产生式产生式A(a|b)*重写为重写为A(a|b)A、A；5)产生式产生式A(a|b)A重写为重写为AaA、AbA。因此，因此，G=(S,A,a,b,SaA,A,AaA,AbA,S)。本讲稿第六十四页，共七十四页FSA正规集正规集正规表达式正规表达式DFSANDFSA正规文法正规文法自动机、正规表达式和正规集关系图自动机、正规表达式和正规集关系图本讲稿第六十五页
50、，共七十四页词法分析程序举例词法分析程序举例-识别表达式中单词识别表达式中单词 表达式：表达式：由变量、常量、运算符(+，-，*，/)及括号组成的式子。识别表达式单词的正规式：识别表达式单词的正规式：+|-|*|/|(|)|a(a|d)*|dd*(.dd*|)(e(+|-|)dd*|)字母表：字母表：=+,-,*,/,(,),.,a,d,e，其中a表示英文字母，d表示09数字。识别表达式单词的识别表达式单词的NDFSA:NDFSA:本讲稿第六十六页，共七十四页识别表达式单词的识别表达式单词的DFSA矩阵矩阵:输输入字符状入字符状态态+-*/（）.a ad de e非非终态终态=0=0终态终态=