编译原理第3章(3).ppt

1、北京交通大学于双元,1,3.3 有限自动机(FA),3.3.1 确定的有限自动机（DFA）,一个DFA有以下五个元素组成:,DFA M=（K，f，S0，Z）,其中,K：,状态的集合（有限个状态）,：,允许输入的字符的集合,Vt,f：,状态转换函数，,单值函数KK,S0：,初始状态,S0K,Z：,终止状态集,Z K,f(Si,a)=Sj,北京交通大学于双元,2,讨论：,(1),确定性,f是单值函数,从某一状态读一字符的下一状态唯一确定,有限的,K集合元素个数有限,(2) f 定义的推广,f单值函数KK,K*K,*=+,记为,(S, ),=S,(S,a),=(f(S,a), ),a, *,f(S,

2、a)=Sk,=(Sk, ),=St,St K, :K*K 单值映射,北京交通大学于双元,3,是在*上定义,f是在上定义,包含f, 将和f合并为一个f,记为f(推广后),(3)有限自动机的功能:识别句子,L(M)=,x,|,f(S0,x),Z,x*,特别:f(So, ),=So,且,SoZ,称可为DFA M识别,S0,北京交通大学于双元,4,(4)DFA可非形式地表示成状态图和状态矩阵,例:DFA M=(S,A,B,C,0,1,S,S),(S,0)=B (S,1)=A (A,0)=C (A,1)=S (B,0)=S (B,1)=C (C,0)=A (C,1)=B,101011,(S,101011

3、),=(S,1),01011),=(A,01011),=(C,1011),=(B,011),=(S,11),=(A,1),=S,北京交通大学于双元,5,(5)正则文法G,一定,DFA M,反之,L(G),L(M),北京交通大学于双元,6,3.3.2 非确定的有限自动机(NFA M),一个NFA M有以下五个元素组成,DFA M=(K,f,S0 ,Z),其中:,K:状态的集合(有限状态),: 允许输入的字符集合,f:状态转换函数,多值函数,K 2k(K的所有子集的集合),f(Si,a)= Sk,St ,S0:初始状态 S0K ,Z: 终止状态集 Z K ,北京交通大学于双元,7,讨论:,1) 不

4、确定:f是多值函数,一对多,有限: K有限,2) f定义推广到* 上,K*2k, 记为,(S,)=S,(S，aw）,=(f(S,a),w),设： f(S,a)=S1,S2,.,Sk,=(S1,S2,.,Sk,w),=(Si, w ),i=1,k,将和f合并为一个f,记为f ,北京交通大学于双元,8,(3) NFA M 所确定的语言,L(M )=,x |,f(S0 , x),Z,x*,(4) NFA M 通常用状态转换图来表示,例: NFA M =(S,A,B,C,a,b, f ,S,C),符号串ababb可由此NFA M 所识别.,北京交通大学于双元,9,3.3.3 DFA M与NFA M 的

5、等价性,1、对于上NFA M ,一定,DFA M,L(M),L(M),2、方法:,确定化,读不动作的NFA M ,读动作的NFA M ,最小化,北京交通大学于双元,10,(1) 读不动作的NFA M 的确定化,问题：设有一NFA M=(K, ,f , S0, Z),现构造一上的DFA M=( K,f,S0,Z),使L(M )=L(M),K由K的全部子集组成 K=2K,特别S0=S0 , 映射f的定义,当且仅当f (S1,S2,Si,a)=R1,R2,Rj时,Si、 Rj K,则f(S1,S2,Si,a)=R1,R2,Rj,qi,qj,f(qi, a)=qj,K 2k,北京交通大学于双元,11,

6、DFA M的终态集Z的定义是:,M的某一状态R1,R2,Rj,其中至少含有一个M的一个终态,则R1,R2,RjZ,Z= R1,R2,Rj|R1,R2,RjK 且R1,R2,RjZ ,北京交通大学于双元,12,f (s0,a)=s0 ,s1 ,f (q0,a)= q3,北京交通大学于双元,13,(2) 读动作的NFA M 的确定化,K 2k,定义:,(1)状态q的闭包 _closure(q) q K, q_closure(q),q,到达的状态均属于_closure(q),(2)状态集P的闭包 _closure(P) P K, 若qP,则 q_closure(P), 若qP,q,到达的状态均属于_

7、closure(p),北京交通大学于双元,14,定义:,1、f(S,),=_closure(S),2、f(S,aw),=_closure(p),其中，P=(S，aw）,SK,aVt , w*,北京交通大学于双元,15,方法: 设有一NFA M=(K,f,S0,Z) 现构造一上的DFA M=( K,f,q0,Z) 使L(M)=L(M) q0= _closure(S0) q0 K 对K中任一尚未标记的状态qi=Si1,Si2,Sim Sik K 做标记qi; 对于每一a ,置 T= f(Si1,Si2,Sim , a); qj= _closure(T);,北京交通大学于双元,16, 若qj不在K中

8、,则将qj作为一未加标记的状态 加 入K中, f(qi,a)= qj, 添加到M上 a (3)重复步骤(2),直到K中不再含有未标记的 状态为止. (4)若某一qj Z ,则qj Z,qi,qj,北京交通大学于双元,17,q0= S1,S2 , S3, S0,q0= _closure(S0),= S0, S1,S2 ,S3,f(q0 ,a)=,_closure(f(q0,a),= S1,S2 , S3, S0,=q0,q0,S1 , S2=q1,q0,a,q1,S2 , S3,=q2,q1 =S1 , S2,q2=S2 , S3,q1,b,q2,q2,c,c,q0,q1,q2,b,北京交通大学

9、于双元,18,3.4正规表达式与正规集 3.4.1正则表达式与正规集 正则式：描述单词符号 正规集：正规式描述的语言 1、正则式的递归定义 设有字汇表V , 则: (VT就是) (1)，a， aVt都是正则表达式, 正规集, , a,北京交通大学于双元,19,(2)如果e1和e2是正则式,正规集分别为L1和L2 则 e1| e2是正则式,正规集为L1L2 e1e2是正则式,正规集为L1L2 e1*是正则式, 正规集为L1* 注: *, , | 的优先级依次降低 例:aVt, bVt, Vt=a,b a是正规式 a*, ba, a|ba* 均是正规式 b是正规式 a|b,(a|b)*, a(a|

10、b)*均是正规式,北京交通大学于双元,20,2、两个正则式相等: 两个正则式表示相同的语言 如(a|b)*=(a*|b*)*, 语言为xxa,b* 3、正则式的操作 结合律(ab)c=a(bc),(a|b)|c=a| (b|c) 交换律a|b=b|a 分配律 a(b|c)=ab|ac,(a|b)c=ac|bc 其他:r|r=r, r*=(r|)*= |r r*,北京交通大学于双元,21,3.4.2 由正则文法构造相应的正则式 求出以 、 | 、 . 表示的文法的语言就是正则式, 用=代替, 用+代替|求出联立方程组的解 1、文法 xrx|t 右线性 r,t Vt+ Lx=LrLxLt 为求解方便写成 x=rx+t 解方程求x 又x=rx=rrx, Lx =t,rt,rrt,即 r*t 可解得x=r*t 论断3.1:方程组x=r x+t有形如x=r*t的解,北京交通大学于双元,22,2、文法 x=xr|t 左线性 r,t Vt+ Lx= Lx LrLt 为求解方便写成 x=xr+t 解方程求x 又x=xr=xrr, Lx =t,tr,trr,即 tr* 可解得x=tr* 论断3.2:方程组x=xr+t有形如x=tr*的解,北京交通