第3章有穷自动机优秀课件.ppt-淘文阁

资源描述

《第3章有穷自动机优秀课件.ppt》由会员分享，可在线阅读，更多相关《第3章有穷自动机优秀课件.ppt（74页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第第3章章有穷自动机有穷自动机第1页，本讲稿共74页有穷自动机有穷自动机(也称有限自动机)作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。有穷自动机分为两类：确定的有穷自动机(Deterministic Finite State Automata)和不确定的有穷自动机(NonDeterministic Finite State Automata)。第2页，本讲稿共74页FSA例例3.1 :识别一个由带符号或无符号十进制数组成的语言。识别一个由带符号或无符号十进制数组成的语言。开

2、始状态终止状态第3页，本讲稿共74页有穷自动机有穷自动机有穷自动机有穷自动机DFSADFSA定义定义定义定义3.13.1：一个确定的有穷自动机（一个确定的有穷自动机（DFSA）M是一个五元组：是一个五元组：M=（Q，t，q0，F）其中其中1 1 Q是一个有穷集，它是一个有穷集，它的每个元素的每个元素的每个元素的每个元素称称为为为为一个一个状态状态状态状态；2 2 是是是是一个有穷字母表，它的每个元素称为一个输入符号，所一个有穷字母表，它的每个元素称为一个输入符号，所以也称以也称为为输入符号字母表输入符号字母表输入符号字母表输入符号字母表；3 3 t t t t是转换函数是转换函数是转换函数是转

3、换函数，是在，是在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是是是是一个一个终止状态集终止状态集终止状态集终止状态集，它至少由一个终止状态组成。，它至少由一个终止状态组成。第4页，本讲稿共74页状态转换表状态转换表例3.1状态转换表第5页，本讲稿共74页DFSA 例例

4、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第6页，本讲稿共74页状态转换表状态转换表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字符状态第7页，本讲稿共74页DFSA 的状态图表示的状态图表示t（q0，a）=q1 t（q2，a）=q3t（q0，b）=q3

5、t（q2，b）=q1t（q1，a）=q0t（q3，a）=q2t（q1，b）=q2 t（q3，b）=q0bq2q1q3q0aaabbab第8页，本讲稿共74页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)=3f(3，a)=3 f(3，b)=3状态转换矩阵状态转换矩阵0312aaaa状态转换图状态转换图bbbb第9页，本讲稿共74页构型和移动构型和移动对于给定的输入串，假定对于给定的输入串，假定DFSA已经完成了若干次移动，已经完成了若干次移动，为了预测它的

6、进一步行为，只需要知道为了预测它的进一步行为，只需要知道“当前状态当前状态”和和“尚待尚待扫描输入串扫描输入串”。对它的描述称为。对它的描述称为构型构型，记为，记为(q,),其中其中q是一个是一个状态，状态，是尚待输入的符号串。是尚待输入的符号串。(q0,)-初始构型初始构型(q,)-终止构型终止构型(q,a)(q,)其中其中a,*用用符号表示自动机的移动，即从一种构型到另一种构型的符号表示自动机的移动，即从一种构型到另一种构型的转换转换DFSA的工作过程就是进行一系列的移动的过程。的工作过程就是进行一系列的移动的过程。*表示表示0次移动或多次移动。次移动或多次移动。+表示表示？DFSA 所识

7、别的语言所识别的语言L(M):L(M)=*|(q0,)*(q,)qF 第10页，本讲稿共74页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），），），），）其中其中qQ，a，*DFSA=(Q,DFSA=(Q,t,q0,F)，如果如果如果如果t t（q0q0，）=q=qF,则符号串则符号串可可可可被有穷自动机被有穷自动机被有穷自动机被有穷自动机DFSADFSA所接受。所接受。所接受。所接受。有穷自动机有穷自动

8、机有穷自动机有穷自动机DFSADFSA所接受的符号串集，记为所接受的符号串集，记为所接受的符号串集，记为所接受的符号串集，记为L(M).L(M).DFSA 可接受的符号串可接受的符号串第11页，本讲稿共74页例例3 3.2中的有穷自动机中的有穷自动机A，t(q0,aabb)=t(t(q0,a),abb)=t(q1,abb)=t(t(q1,a),bb)=t(q0,bb)=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）=q

9、0t（q3，a）=q2t（q1，b）=q2 t（q3，b）=q0bq2q1q3q0aaabbab第12页，本讲稿共74页自动机的等价自动机的等价定义定义3.2 给定两个有穷自动机给定两个有穷自动机M和和M，如果如果L(M)=L(M)，则称自动则称自动机机M和和M等价。等价。例例3.DFSA M=(q0,q1,a,b,t,q0,q0),其中其中t(q0,a)=q1,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等价。等

10、价。第13页，本讲稿共74页非确定的有穷自动机非确定的有穷自动机NDFSA定义定义3.一个非确定的有穷自动机是一个五元组，一个非确定的有穷自动机是一个五元组，NDFA=Q，t，Q0，F，其中其中QQ为状态为状态为状态为状态的有穷非空的有穷非空集集集集，为为为为有穷输入有穷输入字母表字母表字母表字母表，t t为为为为Q 到到Q的子集的子集(多值映射多值映射多值映射多值映射)，QQ0 0 Q是初始状态是初始状态集集集集，F F Q为终止状态集为终止状态集为终止状态集为终止状态集。一个确定的有穷自动机（一个确定的有穷自动机（DFSA）M是一个五元组：是一个五元组：M=（Q，t，q0，F）其中其中1

11、1 Q是一个有穷集，它是一个有穷集，它的每个元素的每个元素的每个元素的每个元素称称为为为为一个一个状态状态状态状态；2 2 是是是是一个有穷字母表，它的每个元素称为一个输入符号，所以也称一个有穷字母表，它的每个元素称为一个输入符号，所以也称为为输入符号字母输入符号字母输入符号字母输入符号字母表表表表；3 3 t t t t是转换函数是转换函数是转换函数是转换函数，是在，是在QQ上的映射，即，如上的映射，即，如:t=(:t=(q，x）=q，（，（q，q Q）就就意味着，当前状态为意味着，当前状态为q q，输入符为输入符为x x时，将转换为下一个状态时，将转换为下一个状态q，我们把我们把q称作称作

12、q q的一个后的一个后继状态；继状态；4 q0 Q Q是唯一是唯一是唯一是唯一的一个的一个开始状态开始状态开始状态开始状态；5 5 F F F F Q是是是是一个一个终止状态集终止状态集终止状态集终止状态集，它至少由一个终止状态组成。，它至少由一个终止状态组成。第14页，本讲稿共74页例子例子NDFSA N=（S，P，Z，0，1，t，S，P，Z）其中其中 t（S，0）=Pt（S，1）=S，Zt（P，1）=Zt（Z，0）=Pt（Z，1）=PSPZ00,1111N状态图表示状态图表示第15页，本讲稿共74页例子例子3.6NDFSA=（Q，t，Q0，F）其中 Q=q0,q1,q2,q3,=x,y,Q

13、0=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第16页，本讲稿共74页NDFSA与与DFSA的区别的区别NDFSA有一个开始状态集合，而有一个开始状态集合，而DFA只有一个开始状只有一个开始状态；态；NDFSA的映射是的映射是Q Q的子集，是一个多值的子集，是一个多值映射，映射，而而DFSA是是Q Q的一个单值的一个单值映射。映射。第17页，本讲稿共74页例例3

14、.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,q1,q3q1 t(q0,xyx)=q0,q1,q3,q0,q1,q3,q1 F所以所以xyx能被该能被该NDFSA所接受。所接受。第18页，本讲稿共74页空移环路的寻找空移环路的寻找如果自动机的弧上允许标记如果自动机的弧上允许标记，则称此自动，则

15、称此自动机为机为自动机，记为自动机，记为 NDFSA或或 DFSA.q1q2 q1q2 q3 q1q2q3 qn(a)(b)(c)第19页，本讲稿共74页空移环路的消除空移环路的消除找到空移环路之后，要消除它只要把空移环路上所有结点找到空移环路之后，要消除它只要把空移环路上所有结点q1,q2,qn合成一个结点，并消除它们所有的合成一个结点，并消除它们所有的弧。如弧。如果其中的某一个结点果其中的某一个结点qi(i=1或或2,n)是开始结点或终止是开始结点或终止结点，则将此合并后的新结点相应地设置为开始状态或结点，则将此合并后的新结点相应地设置为开始状态或终止状态。终止状态。q0q1 q2aq

16、3q4 abbbq0q2aq3bbba(1)(2)例例3.8第20页，本讲稿共74页确定化确定化-子集法子集法(自学自学)给定一个给定一个NDFSA A=(Q,Q,t,Q0,F)是一个非确定的有穷自动机，是一个非确定的有穷自动机，一定可以构造一个和它等价的确定有穷自动机一定可以构造一个和它等价的确定有穷自动机DFSA A=(Q,Q,t,q0,F)，即即L(A)=L(A)。构造步骤构造步骤：(1)A与与 A的字母表的字母表完全相同；完全相同；(2)把把A的每一个的每一个状态子集状态子集作为作为A的一个状态；的一个状态；(3)对对A的任意状态子集的任意状态子集r1,r2,rn，riQ(i=1,2,

17、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 .第21页，本讲稿共74页例例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（q

18、2，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: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

19、,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第22页，本讲稿共74页确定化确定化-造表法造表法子集法的确定，如果状态数子集法的确定，如果状态数n很大，确定化后的状很大，确定化后的状态数将更大态数将更大2n-1，并且其中很多是不可到达的状态并且其中很多是不可到达的状态而造表法，更加简单而有

20、效。而造表法，更加简单而有效。步骤：步骤：确定确定DFSA的的开始状态开始状态，从开始状态开始分别计算对不，从开始状态开始分别计算对不同输入字母的映象，如果产生新的状态，则继续计算同输入字母的映象，如果产生新的状态，则继续计算新状态的映象，重复这个过程一直到没有新的状态出新状态的映象，重复这个过程一直到没有新的状态出现为止。现为止。第23页，本讲稿共74页造表法确定化造表法确定化输入输入状态状态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 q4q

21、1,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第24页，本讲稿共74页确定化后的状态转换图确定化后的状态转换图q0q2xq4xxyyxyq3q1q5yx,yx,y第25页，本讲稿共74页 NDFA的确定化的确定化-闭包、弧转换闭包、弧转换：对于状态集合：对于状态集合I，可以定义以下两种运算，可以定义以下两种运算-closure(I)：称为状态集合：称为状态集合I的的-闭包，其中：闭包，其中：如果如果sI，则有，则有s-closure(I)；如果如果sI，s是从

22、是从s出发经过任意条出发经过任意条弧能弧能够到够到达的状态，则有达的状态，则有s-closure(I)。move(I,a)：称为状态集合称为状态集合I的的a弧转换。该集合是从弧转换。该集合是从I中的某一中的某一状态出发经过一条状态出发经过一条a弧到达的状态结的全体。弧到达的状态结的全体。设设I=s1,s2,.,sn，则有，则有 move(I,a)=f(s1,a)f(s2,a).f(sn,a)。NDFA的确定化包含去掉空移、和空环路及确定化的功能。的确定化包含去掉空移、和空环路及确定化的功能。第26页，本讲稿共74页例例:-closure(0)-closure(1,3)move(2,7,9

23、,a)=0,1,2,4,7=1,2,3,4,6,7=3,8第27页，本讲稿共74页NDFSA到到DFSA的转换：的转换：对于每个对于每个NFSA N=(KN,N,fN,SN,ZN)，存在一个，存在一个DFSA M=(KM,M,fM,SM,ZM)，使得，使得L(M)=L(N)。具。具体转换步骤如下：体转换步骤如下：1)令令M=N；2)设设N=a1,a2,.,an，则构造一个含有，则构造一个含有n+1列的表格，其中第列的表格，其中第1列标记为状态列标记为状态T，第，第2n+1列分别标记为列分别标记为fM(T,a1),.,fM(T,an)。其。其中中fM(T,ai)=-closure(move(T,

24、ai)；3)置该表的第置该表的第1行第行第1列为列为T0=-closure(SN)；4)根据第根据第1列分别计算同一行其他各列的值。如果该值未曾出列分别计算同一行其他各列的值。如果该值未曾出现在第现在第1列，则把它命名为列，则把它命名为Ti并填入到下面空行的第并填入到下面空行的第1列位置上；列位置上；5)重复第重复第4步，直至某行第步，直至某行第2n+1列的所有元素全都出现在第列的所有元素全都出现在第1列上为止；列上为止；6)令令SM=第第1行第行第1列元素列元素T0；7)如果如果Ti含有含有ZN的元素，则令的元素，则令Ti ZM。第28页，本讲稿共74页2 while（C中存在尚未被标记的子

25、集中存在尚未被标记的子集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为状态为状态K的子集。的子集。1 开始，令开始，令-closure(K0)为为C中唯一成员，并中唯一成员，并且它是未被标记的。且它是未被标记的。第29页，本讲稿共74页例例3.6S521346H abba bb aa例：把下面的例：把下面的NDFSA N转换为等价的转换为等价

26、的DFSA M 第30页，本讲稿共74页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 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,

27、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例中对应的状态转换表例中对应的状态转换表第31页，本讲稿共74页例中对应的状态转换图例中对应的状态转换图第32页，本讲稿共74页例：把下面的例：把下面的NDFSA N=转换为等价的转换为等价的DFSA M 第33页，本讲稿共74页第34页，本讲稿共74页消除不可达状态消除不可达状态在自动机中，从开始状态没有一条路径能在自动机中，从开始状态没有一条路径能达到的状态称

28、为达到的状态称为不可达状态不可达状态。不可达状态。不可达状态对于生成自动机的语言毫无意义，因此，对于生成自动机的语言毫无意义，因此，应从自动机中消除。应从自动机中消除。DFSA的化简的化简第35页，本讲稿共74页01S0S1S50S1S2S71S2S2S51S3S5S70S4S5S60S5S3S10S6S8S01S7S0S11S8S3S6001S0S1S50S1S2S71S2S2S51S3S5S70S5S3S10S7S0S11化简后的结果：左右等价DFSA的化简的化简第36页，本讲稿共74页DFSA的化简的化简对对DFSA化简就是使它的状态数最少，即对任意一个确定的有穷自动化简就是使它的状态数

29、最少，即对任意一个确定的有穷自动机机A，要构造另一个确定的有穷自动机要构造另一个确定的有穷自动机A，使使L(A)=L(A)，且且A的状态个数不超过的状态个数不超过A的状态个数。的状态个数。状态等价：状态等价：如果从状态如果从状态q1出发能扫描任意串出发能扫描任意串w而停止于终态，而停止于终态，那么从状态那么从状态q2出发也能扫描同一个串出发也能扫描同一个串w而停止于终态。则而停止于终态。则DFSA的两个的两个状态状态q1与与q2是等价的是等价的。若。若DFSA的两个状态的两个状态q1与与q2不等价，不等价，则称状态则称状态q1与与q2是是可区分的可区分的。若若q1,q2为为DFSA中的两个状态

30、，若中的两个状态，若 (q1,w)*(s1,),(q2,w)*(t1,)其中其中 w*，且且s1与与t1都为终止状态都为终止状态则则q1,q2等价。等价。第37页，本讲稿共74页DFSA化简的化简的基本思想基本思想是将状态集分解成若干互不相交的是将状态集分解成若干互不相交的子集，使每个子集的状态都是等价的，而不同子集的状态子集，使每个子集的状态都是等价的，而不同子集的状态是不等价的即是可区分的。是不等价的即是可区分的。化简步骤化简步骤(1)将状态集合分解为两个子集合，所有终止状态为一个子集，其将状态集合分解为两个子集合，所有终止状态为一个子集，其他非终止状态为一个子集。他非终止状态为一个子集。

31、(2)对每个子集再进行分解，分解后的两个状态对每个子集再进行分解，分解后的两个状态同于一个，同于一个，当且仅当且仅当对当对任何任何一个输入字母，它们的映象属于同一个子集。一个输入字母，它们的映象属于同一个子集。(3)重复（重复（2）一直到不能再分解为止。）一直到不能再分解为止。第38页，本讲稿共74页如图，状态如图，状态0和和4是可区别的。是可区别的。状态状态2和和3是可区别的，因为读入是可区别的，因为读入b后分别到达后分别到达2和和4，而，而2和和4不是等价的。不是等价的。b02134abaaaabbbDFA M第39页，本讲稿共74页DFSA的化简的化简(书书P62)第40页，本讲稿共7

32、4页1643257aaaaaaabbbbbbb第41页，本讲稿共74页将将M分成两个子集：分成两个子集：一个终态（可接受态）组成，一个非终态组成。一个终态（可接受态）组成，一个非终态组成。P0(1,2,3,4,5,6,7)第第1个子集个子集1,2,3,4中：中：1,2中的状态和中的状态和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可有输入符

33、号可有输入符号a或或b，分割为：，分割为：第42页，本讲稿共74页1643257aaaaaaabbbbbbbP3(1,2,3,4,5,6,7)1,2,6,7不能再分割，也即等价的。16435aaaaabbbbb第43页，本讲稿共74页书书P64例例 q0q2xq4xxyyxyq3q1q5yx,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分解为两个子集分解为两

34、个子集S1=q1,S2=q3,q4,q5。因为因为t(q0,x)=q1 S1,t(q2,x)=q3 S2,所以将所以将S2分解成分解成q0 q2q0q2xyxyq1q3yx,yx第44页，本讲稿共74页从从DFA到程序表示到程序表示如果对如果对DFA的每个状态都事先指明它所要完成的任务，的每个状态都事先指明它所要完成的任务，再把从状态发出的弧上所标记的输入字母作看作控制条件，再把从状态发出的弧上所标记的输入字母作看作控制条件，那么，那么，DFA实际上是一个程序流程图。实际上是一个程序流程图。q0q1q2l,dl非非l,d标识符DFAchar ch,namekname=read(ch)name=

35、name+chread(ch)用name查找符号表，若没有，则填表，否则返回其地址q0q1q2ch=lch=l or d非l,d标识符程序流程图第45页，本讲稿共74页课堂练习课堂练习:将下面将下面NDFSA状态转换图，转换为状态转换图，转换为DFSA状状态转换图，并化简。态转换图，并化简。SBZ00,1A C1第46页，本讲稿共74页第47页，本讲稿共74页从正规文法到从正规文法到FSA(自动机自动机)对于正规文法对于正规文法G可以直接构造一个有穷自动机可以直接构造一个有穷自动机A，使使L（A）=L（G）。）。构造步骤：构造步骤：(1)正规文法正规文法G中终结符号集作为中终结符号集作为A的字

36、母输入表；的字母输入表；(2)文法文法G的每个非终结符号都作为的每个非终结符号都作为A的一个状态，文法的一个状态，文法的开始符号作为的开始符号作为A的开始状态；的开始状态；(3)在自动机在自动机A中增加一个新状态中增加一个新状态z作为自动机的终止状态；作为自动机的终止状态；(4)对文法对文法G中形如中形如UaV(a VT或或a=,V VN)的产生的产生式，在自动机式，在自动机A中构造形如中构造形如t(U,a)=V的映射；的映射；(5)对文法对文法G中形如中形如Ua(a VT)的产生式，在自动机的产生式，在自动机A中中构造形如构造形如t(U,a)=z的映射；的映射；第48页，本讲稿共74页例：例

37、：设正规文法设正规文法G19S：SaS|aA|bB,AbA|cC,BaB|dD,CcC|c,DdD|d由文法由文法G19构造的构造的FSA：SZDBCAaabbcadccdd第49页，本讲稿共74页例：设例：设GS=SaA,SbB,S,AaB,AbA,BaS,BbA,B，则相应的，则相应的NFSA如下：如下：第50页，本讲稿共74页从从DFSA到正规文法到正规文法构造步骤：构造步骤：(1)自动机的每个状态标记均作为正规文法的非终结符，自动机的每个状态标记均作为正规文法的非终结符，其中自动机开始符号的标记作为文法的开始符号。自其中自动机开始符号的标记作为文法的开始符号。自动机的输入字母表中的所有

38、符号作为正规文法的终结动机的输入字母表中的所有符号作为正规文法的终结符；符；(2)对于自动机的映射对于自动机的映射t(U,a)=V（其中其中U,V是自动机的状是自动机的状态标记，态标记，a为输入符号），构造文法的一条产生式为输入符号），构造文法的一条产生式UaV,U,V非终结符，非终结符，a终结符；终结符；(3)对于自动机的终止状态对于自动机的终止状态Z，在正规文法中增加一条产在正规文法中增加一条产生式：生式：Z 。第51页，本讲稿共74页例例3.11构造的正规文法构造的正规文法G21S：SxA|yBAyA|yC|xBBxC|yC|yA|C CASyx,yyByxxy第52页，本讲稿共74页正

39、规表达式的定义正规表达式的定义定义定义3.9 字母表字母表上的正规表达式和正规集递归定义如下：上的正规表达式和正规集递归定义如下：(1)a ,a是是上的一个正规表达式，它所表示的正规集为上的一个正规表达式，它所表示的正规集为a;(2)空串空串是是上的一个正规表达式上的一个正规表达式,它所表示的正规集为它所表示的正规集为;(3)空集空集是是上的一个正规表达式上的一个正规表达式,它所表示的正规集为它所表示的正规集为;(4)设设e1,e2都是都是上的正规表达式，它们表示的正规集分别为上的正规表达式，它们表示的正规集分别为L(e1)和和L(e2)，则：则：i)e1|e2也是正规表达式，它所表示的正规

40、集为也是正规表达式，它所表示的正规集为L(e1|e2)=L(e1)L(e2);ii)e1.e2也是正规表达式，它所表示的正规集为也是正规表达式，它所表示的正规集为L(e1.e2)=L(e1)L(e2);ii)(e1)*也是正规表达式，它所表示的正规集为也是正规表达式，它所表示的正规集为L(e1)*)=(L(e1)*.第53页，本讲稿共74页正规表达式的性质正规表达式的性质定义定义3.10 设设e1,e2是是上的正规表达式，若上的正规表达式，若L(e1)=L(e2)，则则e1与与e2等价，记为等价，记为e1=e2.如如a|(ba)*=(ba)*|a.定理定理3.1设设e1,e2是是上的正规表达式

41、，则上的正规表达式，则(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=e1 =e1第54页，本讲稿共74页正规式正规集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，则有：第55页，本讲稿共74页正规式和有穷自动机的等价性正规

42、式和有穷自动机的等价性1.对于对于上的上的NDFSA M，可以构造一个，可以构造一个上的正规式上的正规式e,e,使得使得L(e)=L(M)。2.2.对于对于上的一个正规式上的一个正规式e，可以构造一个，可以构造一个上的上的NDFSA M，使得，使得L(M)=L(e)。第56页，本讲稿共74页正规表达式到正规表达式到NDFSA的转换的转换步骤步骤:(1)先构造一个广义的先构造一个广义的NDFA转换图，只有转换图，只有S，Z两个状态，两个状态，S是开始状态，是开始状态，Z是终止状态，弧上是正规表达式是终止状态，弧上是正规表达式e;(2)按照下面替换按照下面替换规则，对规则，对e进行分解，直到转换图

44、 x1 y7 x x4y yx x第58页，本讲稿共74页NDFSA到正规表达式的转换到正规表达式的转换步骤步骤:(1)在在NDFSA中新设置中新设置一个唯一的开始状态一个唯一的开始状态S和唯和唯一的终止状态一的终止状态Z；(2)从开始状态从开始状态S到原来的到原来的开始状态连接开始状态连接弧，再从原弧，再从原来的终止状态到来的终止状态到Z状态也连状态也连接接弧；弧；(3)按照替换规则进行按照替换规则进行替换，直到状态图中只剩替换，直到状态图中只剩下下S和和Z，在在S，Z弧上的表达弧上的表达式就是所求的结果。式就是所求的结果。第59页，本讲稿共74页第60页，本讲稿共74页从正规文法与正规

45、表达式从正规文法与正规表达式产生式产生式正规式正规式规则规则1 1AxBAxB、ByByA=xyA=xy规则规则2 2AxA|yAxA|yA=xA=x*y y规则规则3 3AxAx、AyAyA=x|yA=x|y正规文法正规文法G=(VN,VT,P,S)到正规式到正规式r的转换：的转换：利用以下转换利用以下转换规则生成产生式，最后只剩下一个产生式，该产生式的规则生成产生式，最后只剩下一个产生式，该产生式的左部为文法的开始符号左部为文法的开始符号S，右部不含非终结符号。，右部不含非终结符号。一个语言可以由正规文法定义，也可以由正规式定义。一个语言可以由正规文法定义，也可以由正规式定义。对任何一个正

46、规文法，存在一个定义同一个语言的正规对任何一个正规文法，存在一个定义同一个语言的正规式；反之，对每个正规式，存在一个生成同一个语言的式；反之，对每个正规式，存在一个生成同一个语言的正规文法。正规文法。第61页，本讲稿共74页例：正规文法例：正规文法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)*。第62页，本讲稿共74页正规式正规式r到正规文法到正规文法G=(VN,VT,P,S)的转换：的转换：具

47、体转换步骤如下。具体转换步骤如下。1)令令VT=；2)令令S为为G的开始符号，的开始符号，VN=S，生成产生式，生成产生式Sr；3)如果如果x、y是正规式，则对形如是正规式，则对形如Axy的产生式，重写为的产生式，重写为AxB和和By两个产生式，并把两个产生式，并把B加到加到VN；4)如果如果x、y是正规式，则对形如是正规式，则对形如Ax*y的产生式，重写为的产生式，重写为AxA、Ay两个产生式；两个产生式；5)如果如果x、y是正规式，则对形如是正规式，则对形如Ax|y的产生式，重写为的产生式，重写为Ax和和Ay两个产生式；两个产生式；6)重复步骤重复步骤35，直到，直到G中的每个产生式的右部

49、A,AbA,S)。第64页，本讲稿共74页FSA正规集正规集正规表达式正规表达式DFSANDFSA正规文法正规文法自动机、正规表达式和正规集关系图自动机、正规表达式和正规集关系图第65页，本讲稿共74页词法分析程序举例词法分析程序举例-识别表达式中单词识别表达式中单词表达式：表达式：由变量、常量、运算符(+，-，*，/)及括号组成的式子。识别表达式单词的正规式：识别表达式单词的正规式：+|-|*|/|(|)|a(a|d)*|dd*(.dd*|)(e(+|-|)dd*|)字母表：字母表：=+,-,*,/,(,),.,a,d,e，其中a表示英文字母，d表示09数字。识别表达式单词的识别表达式单词

50、的NDFSA:NDFSA:第66页，本讲稿共74页识别表达式单词的识别表达式单词的DFSA矩阵矩阵:输输入字符状入字符状态态+-*/（）.a ad de e非非终态终态=0=0终态终态=1=10 08 88 88 88 88 88 87 71 10 01 12 21 13 31 12 24 40 03 36 66 65 50 04 44 43 31 15 55 51 16 65 50 07 77 77 71 18 81 1第67页，本讲稿共74页识别表达式单词的识别表达式单词的DFDFA:A:第68页，本讲稿共74页DFSA在计算机中的表示在计算机中的表示DFA=(Q,t,q0,F)中映射中映

展开阅读全文

第3章 有穷自动机优秀课件.ppt

第3章有穷自动机优秀课件.ppt