第4章--正则表达式-计算机专业-形式语言.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,2026/10/21,1,第,4,章 正则表达式,正则文法擅长语言的产生，有穷状态自动机擅长语言的识别。,本章讨论正则语言的正则表达式描述。它在对正则语言的表达上具有特殊的优势，为正则语言的计算机处理提供了方便条件。,简洁、更接近语言的集合表示和语言的计算机表示等。,2026/10/21,2,第,4,章 正则表达式,主要内容,典型,RE,的构造。,与,RE,等价,FA,的构造方法。,与,DFA,等价的,RE,的构造。,重点,RE,的概念。,RE,与,DFA,的等价性。,难点：,RE,与,DFA,的等价性证明。,2026/10/21,3,4.,启示,产生语言,a,n,b,m,c,k,|n,，,m,，,k,1,a,i,c,n,bxa,m,|i,0,n,1,m,2,x,为,d,和,e,组成的串,的正则文法为,A,aA|aB|cE,B,bB|bC,C,cC|c,E,cE|bF,F,dF|eF|aH,H,aH|a,2026/10/21,4,4.,启示,接受此语言的,NFA M,2026/10/21,6,4.,启示,set(E)=set(A)cc,*,=a,*,cc,*,=a,*,c,+,set(F)=set(E)bd,，,e,*,=a,*,c,+,bd,，,e,*,set(H)=set(F)aa,*,=a,*,c,+,bd,，,e,*,aa,*,=a,*,c,+,b d,，,e,*,a,+,set(I)=set(H)a=a,*,c,+,b d,，,e,*,a,+,a,L(M)=set(D),set(H),=a,+,b,+,c,+,a,*,c,+,bd,，,e,*,a,+,a,2026/10/21,7,4.,启示,根据集合运算的定义，,d,，,e=d,e,。,从而，,d,，,e,*,=(d,e),*,。,这样可以将,L(M),写成如下形式：,L(M)=a,+,b,+,c,+,a,*,c,+,b(d,e),*,a,+,a,记作：,a,+,b,+,c,+,+a,*,c,+,b(d+e),*,a,+,a=aa,*,bb,*,cc,*,+a,*,cc,*,b(d+e),*,aaa,*,2026/10/21,8,4.2 RE,的形式定义,正则表达式,(regular expression,，,RE),是上的,RE,，它表示语言,；,是上的,RE,，它表示语言,；,对于,a,，,a,是上的,RE,，它表示语言,a,；,2026/10/21,10,4.2 RE,的形式定义,例,4-1,设,=0,，,1,0,，表示语言,0,；,1,，表示语言,1,；,(0+1),，表示语言,0,，,1,；,(01),，表示语言,01,；,(0+1),*,),，表示语言,0,，,1,*,；,(00)(00),*,),，表示语言,0000,*,；,2026/10/21,11,4.2 RE,的形式定义,(0+1),*,)(0+1)(0+1),*,),表示语言,0,，,1,+,；,(0+1),*,)000)(0+1),*,),，表示,0,，,1,上的至少含有,3,个连续,0,的串组成的语言；,(0+1),*,)0)1),，表示所有以,01,结尾的,0,、,1,字符串组成的语言；,(1(0+1),*,)0),，表示所有以,1,开头，并且以,0,结尾的,0,、,1,字符串组成的语言。,2026/10/21,13,4.2 RE,的形式定义,(0+1),*,)(0+1)(0+1),*,)=(0+1),*,(0+1)(0+1),*,在意义明确时，,RE r,表示的语言记为,L(r),，也可以直接地记为,r,。,加、乘、闭包运算均执行左结合规则。,2026/10/21,15,4.2 RE,的形式定义,交换律：,r+s=s+r,。,幂等律：,r+r=r,。,加法运算零元素：,r+,=r,。,乘法运算单位元：,r=r=r,。,乘法运算零元素：,r,=,r=,。,L(,)=,。,L()=,。,L(a)=a,。,2026/10/21,16,4.2 RE,的形式定义,L(rs)=L(r)L(s),。,L(r+s)=L(r)L(s),。,L(r,*,)=(L(r),*,。,L(,*,)=,。,L(r+),*,)=L(r*),。,L(r,*,),*,)=L(r,*,),。,L(r,*,s,*,),*,)=L(r+s),*,),。,如果,L(r),L(s),，则,r+s=s,。,2026/10/21,18,4.2 RE,的形式定义,例,4-2,设,=0,，,1,00,表示语言,00,；,(0+1),*,00(0+1),*,表示所有的至少含两个连续,0,的,0,、,1,串组成的语言；,(0+1),*,1(0+1),9,表示所有的倒数第,10,个字符为,1,的串组成的语言；,2026/10/21,19,4.2 RE,的形式定义,L(0+1),*,011)=x|x,是以,011,结尾的,0,、,1,串,；,L(0,+,1,+,2,+,)=0,n,1,m,2,k,|m,，,n,，,k1,；,L(0,*,1,*,2,*,)=0,n,1,m,2,k,|m,，,n,，,k0,；,L(1(0+1),*,1+0(0+1),*,0)=x|x,的开头字符与尾字符相同,。,2026/10/21,20,4.3 RE,与,FA,等价,正则表达式,r,称为与,FA M,等价，如果,L(r)=L(M),。,从开始状态出发，根据状态之间按照转移所确定的后继关系，依次计算出所给,FA,的各个状态,q,对应的,set(q),，并且最终得到相应的,FA,接受的语言的,RE,表示。,寻找一种比较“机械”的方法，使得计算机系统能够自动完成,FA,与,RE,之间的转换。,2026/10/21,21,4.3.1 RE,到,FA,的等价变换,0,对应的,FA,01,对应的,FA,2026/10/21,22,4.3.1 RE,到,FA,的等价变换,0+1,对应的,FA,2026/10/21,24,4.3.1 RE,到,FA,的等价变换,定理,4-1 RE,表示的语言是,RL,。,证明：,施归纳于正则表达式中所含的运算符的个数,n,，证明对于字母表上的任意正则表达式,r,，存在,FA M,，使得,L(M)=L(r),。,M,恰有一个终止状态。,M,在终止状态下不作任何移动。,2026/10/21,25,4.3.1 RE,到,FA,的等价变换,n=0,r=,r=,r=a,2026/10/21,26,4.3.1 RE,到,FA,的等价变换,设结论对于,n=k,时成立，此时有如下,FA,：,M,1,=(Q,1,，,1,，,q,01,，,f,1,),M,2,=(Q,2,，,2,，,q,02,，,f,2,),L(M,1,)=L(r,1,),，,L(M,2,)=L(r,2,),。,Q,1,Q,2,=,。,n=k,2026/10/21,28,4.3.1 RE,到,FA,的等价变换,n=k+1,r=r,1,+r,2,2026/10/21,29,4.3.1 RE,到,FA,的等价变换,M=(Q,1,Q,2,，,，,q,01,，,f,2,),对,q,Q,1,-f,1,，,a,(q,，,a)=,1,(q,，,a),；,对,q,Q,2,-f,2,，,a,(q,，,a)=,2,(q,，,a),；,(f,1,，,)=q,02,2026/10/21,31,4.3.1 RE,到,FA,的等价变换,M=(Q,1,q,0,，,f,，,，,q,0,，,f),其中,q,0,，,f,Q,1,，定义,为,对,q,Q,1,-f,1,，,a,，,(q,，,a)=,1,(q,，,a),。,(f,1,，,)=q,01,，,f,。,(q,0,，,)=q,01,，,f,。,2026/10/21,32,4.3.1 RE,到,FA,的等价变换,r=r,1,*,2026/10/21,33,4.3.1 RE,到,FA,的等价变换,按照定理,4-1,证明给出的方法构造一个给定,RE,的等价,FA,时，该,FA,有可能含有许多的空移动。,可以按照自己对给定,RE,的,“,理解,”,以及对,FA,的,“,理解,”,“,直接地,”,构造出一个比较,“,简单,”,的,FA,。,定理证明中所给的方法是机械的。由于,“,直接地,”,构造出的,FA,的正确性依赖于构造者的,“,理解,”,，所以它的正确性缺乏有力的保证。,2026/10/21,34,4.3.1 RE,到,FA,的等价变换,例,4-3,构造与,(0+1),*,0+(00),*,等价的,FA,。,2026/10/21,35,4.3.1 RE,到,FA,的等价变换,按照对,(0+1),*,0+(00),*,的,“,理解,”,“,直接地,”,构造出的,FA,。,2026/10/21,36,4.3.2 RL,可以用,RE,表示,计算,DFA,的每个状态对应的集合,字母表的克林闭包的等价分类，是具有启发意义的。,这个计算过程难以,“,机械,”,地进行。,计算,q,1,到,q,2,的一类串的集合：,R,k,ij,。,图上作业法。,2026/10/21,37,4.3.2 RL,可以用,RE,表示,定理,4-2,RL,可以用,RE,表示。,设,DFA,M=(q,1,，,q,2,，,，,q,n,，,，,q,1,，,F),R,k,ij,=x|,(q,i,，,x)=q,j,而且对于,x,的任意前缀,y(y,x,，,y,),，如果,(q,i,，,y)=q,l,，则,l,k,。,2026/10/21,38,4.3.2 RL,可以用,RE,表示,R,0,ij,=,a|,(q,i,，,a)=q,j,如果,i,j,a|,(q,i,，,a)=q,j,如果,i=j,R,k,ij,=R,k-1,ik,(R,k-1,kk,),*,R,k-1,kj,R,k-1,ij,2026/10/21,39,4.3.2 RL,可以用,RE,表示,图上作业法,启示,2026/10/21,40,4.3.2 RL,可以用,RE,表示,图上作业法操作步骤,预处理：,用标记为,X,和,Y,的状态将,M,“,括起来,”,：,在状态转移图中增加标记为,X,和,Y,的状态，从标记为,X,的状态到标记为,q,0,的状态引一条标记为,的弧；从标记为,q(q,F),的状态到标记为,Y,的状态分别引一条标记为,的弧。,去掉所有的不可达状态。,2026/10/21,41,4.3.2 RL,可以用,RE,表示,对通过步骤,(1),处理所得到的状态转移图重复如下操作，直到该图中不再包含除了标记为,X,和,Y,外的其他状态，并且这两个状态之间最多只有一条弧。,并弧,将从,q,到,p,的标记为,r,1,，,r,2,，,，,r,g,并行弧用从,q,到,p,的、标记为,r,1,+r,2,+,+r,g,的弧取代这,g,个并行弧。,2026/10/21,42,4.3.2 RL,可以用,RE,表示,去状态,1,如果从,q,到,p,有一条标记为,r,1,的弧，从,p,到,t,有一条标记为,r,2,的弧，不存在从状态,p,到状态,p,的弧，将状态,p,和与之关联的这两条弧去掉，用一条从,q,到,t,的标记为,r,1,r,2,的弧代替。,去状态,2,如果从,q,到,p,有一条标记为,r,1,的弧，从,p,到,t,有一条标记为,r,2,的弧，从状态,p,到状态,p,标记为,r,3,的弧，将状态,p,和与之关联的这三条弧去掉，用一条从,q,到,t,的标记为,r,1,r,3,*,r,2,的弧代替。,2026/10/21,43,4.3.2 RL,可以用,RE,表示,去状态,3,如果图中只有三个状态，而且不存在从标记为,X,的状态到达标记为,Y,的状态的路，则将除标记为,X,的状态和标记为,Y,的状态之外的第,3,个状态及其相关的弧全部删除。,2026/10/21,44,4.3.2 RL,可以用,RE,表示,从标记为,X,的状态到标记为,Y,的状态的弧的标记为所求的正则表达式。如果此弧不存在，则所求的正则表达式为,。,2026/10/21,45,4.3.2 RL,可以用,RE,表示,例,4-4,求图,4-14,所示的,DFA,等价的,RE,。,2026/10/21,46,4.3.2 RL,可以用,RE,表示,预处理。,2026/10/21,47,4.3.2 RL,可以用,RE,表示,去掉状态,q,3,。,2026/10/21,48,4.3.2 RL,可以用,RE,表示,去掉状态,q,4,。,2026/10/21,49,4.3.2 RL,可以用,RE,表示,合并从标记为,q,2,的状态到标记为,Y,的状态的两条并行弧。,2026/10/21,50,4.3.2 RL,可以用,RE,表示,去掉状态,q,0,。,2026/10/21,51,4.3.2 RL,可以用,RE,表示,并弧。,2026/10/21,52,4.3.2 RL,可以用,RE,表示,去掉状态,q,1,。,2026/10/21,53,4.3.2 RL,可以用,RE,表示,去掉状态,q,2,。,1,*,0(11,*,0),*,0(00,*,111,*,0+00,*,10+11,*,0)(11,*,0),*,0)(00,*,+00,*,1),就是所求。,2026/10/21,54,4.3.2 RL,可以用,RE,表示,几点值得注意,的问题,如果去状态的顺序不一样，则得到的,RE,可能在形式是不一样，但它们都是等价的。,当,DFA,的终止状态都是不可达的时候，状态转移图中必不存在从开始状态到终止状态的路。,此时，相应的,RE,为,。,不计算自身到自身的弧，如果状态,q,的入度为,n,，出度为,m,，则将状态,q,及其相关的弧去掉之后，需要添加,n*m,条新弧。,2026/10/21,55,4.3.2 RL,可以用,RE,表示,对操作的步数施归纳，可以证明它的正确性。,推论,4-1,正则表达式与,FA,、正则文法等价，是正则语言的表示模型。,2026/10/21,56,4.4,正则语言等价模型的总结,A,aB B(A,a),A,a q,f,(A,a),(q,a)=p q,ap,(q,a)=pF q,a,RG,G,DFA,NFA,RE,-NFA,DFA,(P,a)=,NFA,(P,a),NFA,(q,，,a),=(q,，,a),图上作业法,归纳,2026/10/21,57,4.5,小结,本章讨论了,RL,及其与,FA,的等价性。,字母表上的,RE,用来表示上的,RL,。,、,、,a,（,a,），是上的最基本的,RE,，它们分别表示语言,、,、,a,，以此为基础，如果,r,和,s,分别是上的表示语言,R,和,S,的,RE,，则,r+s,、,rs,、,r*,分别是上的表示语言,RS,、,RS,、,R*,的,RE,。如果,L(r)=L(s),，则称,r,与,s,等价。,2026/10/21,58,4.5,小结,RE,对乘、加满足结合律；乘对加满足左、右分配律；加满足交换率和幂等率；,是加运算的零元素；,是乘运算的单位元；,是乘运算的零元素。,RE,是,RL,的一种描述。容易根据,RE,构造出与它等价的,FA,。反过来，可以用图上作业法构造出与给定的,DFA,等价的,RE,。,RL,的,5,种等价描述模型转换图。,2026/10/21,59,习题,写出下列语言的正则表达式,0,，,1,*,0,，,1,+,x|,x,0,，,1,+,且,x,的第十个字符是,1,x|,x,0,，,1,+,且,x,以,0,开头以,1,结尾,x|,x,0,，,1,+,且,x,中至少含两个,1,x|,x,0,，,1,*,和,x,如果以,1,结尾，则它的长度为偶数；如果,x,以,0,结尾，则它的长度为奇数,x|,x,0,，,1,*,且,x,中不含形如,00,的子串,2026/10/21,60,习题,理解如下正则表达式，说明它们表示的语言,（,00+11,）,+,(0+01+001),*,(+0+00),(0+1)(0+1),*,+,(0+1)(0+1)(0+1),*,(0+1)(0+1),*,(0+1)(0+1)(0+1),*,构造下列正则表达式的等价,FA,(0+1)(0+1),*,+,(0+1)(0+1)(0+1),*,2026/10/21,61,习题,构造等价如图所示,DFA,的正则表达式,q,0,q,1,q,2,q,3,S,1,1,1,0,0,0,，,1,0,0,