《正则表达式教学.ppt》由会员分享，可在线阅读，更多相关《正则表达式教学.ppt（51页珍藏版）》请在三一办公上搜索。
1、2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,1,第四章 正则表达式,付国宏黑龙江大学计算机科学技术学院,形式语言与自动机理论,2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,2,引言,RG擅长语言的产生；FA擅长语言的识别；正则表达式-正则语言的代数表示在对正则语言的表达上具有特殊的优势；简洁、更接近语言的集合表示和语言的计算机表示等；为正则语言的计算机处理提供了方便条件。,2023/8/19,Guohong Fu,School of Computer Sci&Tech,
2、HLJU,3,提要,主要内容RE的非形式化描述和形式定义典型RE的构造与RE等价FA的构造方法与DFA等价的RE的构造重点RE的概念RE与DFA的等价性难点RE与DFA的等价性证明,2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,4,RE的非形式化描述,基本思想：用代数的方法表示正规语言语义：作用于语言上的三种代数运算两个语言L1和L2的并，记作L1L2L1L2=wwL1或 wL2设L1=001,10,L2=,001，则L1L2=,001,10两个语言L1和L2的连接，记作L1L2 或L1L2 L1L2=w1w2 w1 L1 且 w2
3、 L2L1L2=001,10,001=001,001001,10,10001语言L的(星或克林)闭包，记作L*L*=L0 L1 L2=i 0 Li，其中，L0=，L1=L,L2=LL,Li=Li-1L,L=0,1，则L*表示所有的0和1的串L=0,11，则L*表示使1成对出现的所有的0和1的串,2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,5,RE的形式定义,正则表达式(regular expression，RE)(1)是上的RE，它表示语言；(2)是上的RE，它表示语言；(3)对于a，a是上的RE，它表示语言a；(4)如果r和s分
4、别是上表示语言L(r)和L(s)的RE，则：r与s的“和”(r+s)是上的RE，(r+s)表达的语言为L(r)L(s)，即：L(r+s)=L(r)L(s)；r与s的“乘积”(rs)是上的RE，(rs)表达的语言为L(r)L(s)，即：L(rs)=L(r)L(s)；r的克林闭包(r*)是上的RE，(r*)表达的语言为(L(r)*，L(r*)=(L(r)*。(5)只有满足(1)、(2)、(3)、(4)的才是上的RE。,2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,6,RE的形式定义(cont.),例 4-1 设=0,1(1)0-表示语言
5、0；(2)1-表示语言1；(3)(0+1)-表示语言0,1；(4)(01)-表示语言01；(5)(0+1)*)-表示语言0,1*；(6)(00)(00)*)-表示语言0000*；(7)(0+1)*)(0+1)(0+1)*)-表示语言0,1+；(8)(0+1)*)000)(0+1)*)-表示0,1上的至少含有3个连续0的串组成的语言；(9)(0+1)*)0)1)-表示所有以01结尾的0、1字符串组成的语言；(10)(1(0+1)*)0)-表示所有以1开头，并且以0结尾的0、1字符串组成的语言。,利用RE的定义理解RE表示的语言,2023/8/19,Guohong Fu,School of Com
6、puter Sci&Tech,HLJU,7,RE的形式定义(cont.),RE运算符的优先级闭包运算的优先级最高乘运算“”的优先级次之加运算“+”的优先级最低在意义明确时，可以省略其中某些括号(0+1)*)000)(0+1)*)=(0+1)*000(0+1)*(0+1)*)(0+1)(0+1)*)=(0+1)*(0+1)(0+1)*,2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,8,RE的形式定义(cont.),约定 用r的正闭包r+表示r与(r*)的乘积以及(r*)与r的乘积：r+=rr*=r*r在意义明确时，RE r表示的语言记
7、为L(r)，也可直接记为r；加、乘、闭包运算均执行左结合规则；,2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,9,RE的形式定义(cont.),相等(equivalence)设r、s是字母表上的一个RE，如果L(r)=L(s)，则称r与s相等，记作r=s；相等也称为等价。,2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,10,RE的形式定义(cont.),幂 r是字母表上的RE，r的n次幂定义为 r0=；rn=rn-1r，n1,2023/8/19,Guohong Fu,Sc
8、hool of Computer Sci&Tech,HLJU,11,RE的形式定义(cont.),关于RE运算的一些基本结论 结合律：(rs)t=r(st),(r+s)+t=r+(s+t);分配律：r(s+t)=rs+rt,(s+t)r=sr+tr;交换律：r+s=s+r;幂等律：r+r=r;加法运算零元素：r+=r;乘法运算单位元：r=r=r;乘法运算零元素：r=r=;(8)L()=;(9)L()=;(10)L(a)=a;,2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,12,4.2 RE的形式定义(cont.),(11)L(rs)
9、=L(r)L(s);(12)L(r+s)=L(r)L(s);(13)L(r*)=(L(r)*;(14)L(*)=;(15)L(r+)*)=L(r*);(16)L(r*)*)=L(r*);(17)L(r*s*)*)=L(r+s)*);(18)如果L(r)L(s)，则r+s=s;(19)L(rn)=(L(r)n;(20)rnrm=rn+m;,注意：一般地，r+r，(rs)n rnsn，rssr,2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,13,RE的形式定义(cont.),例 4-2 设=0,100表示语言00；(0+1)*00(0+
10、1)*表示所有的至少含两个连续0的0、1串组成的语言；(0+1)*1(0+1)9表示所有的倒数第10个字符为1的串组成的语言；L(0+1)*011)=x|x是以011结尾的0、1串；L(0+1+2+)=0n1m2k|m,n,k1；L(0*1*2*)=0n1m2k|m,n,k0；L(1(0+1)*1+0(0+1)*0)=x|x的开头字符与尾字符相同。,利用RE的运算律理解RE表示的语言,2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,14,RE与FA的等价变换,AaB B(A,a)Aa qf(A,a),RG,DFA,NFA,RE,-NF
11、A,DFA(P,a)=NFA(P,a),归纳法,图上作业法,(q,a)=pqap(q,a)=pF qa,NFA(q,a)=-NFA(q,a),RL相关模型之间的等价构造关系,2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,15,从RE构造FA的等价变换,归纳法：根据RE的递归定义构造相应的FA(-NFA)(1)基础RE r=对应的FARE r=对应的FARE r=a对应的FA,2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,16,从RE到FA的等价变换(cont.),(2)归
12、纳构造RE r=r1+r2对应的FA设r1M1=Q1,1,q01,qf1,r2M2=Q2,2,q02,qf2；取q0，qfQ1Q2，令 M=(Q1Q2q0,qf,q0,qf)(q0,)=q01,q02;qQ1,a,(q,a)=1(q,a);qQ2,a,(q,a)=2(q,a);(qf1,)=qf,(qf2,)=qf。,2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,17,从RE到FA的等价变换(cont.),构造RE r=r1r2对应的FA设r1M1=Q1,1,q01,qf1,r1M2=Q2,2,q02,qf2；取M=(Q1Q2,q0
13、1,qf2)定义qQ1-qf1,a,(q,a)=1(q,a);qQ2-qf2,a,(q,a)=2(q,a);(qf1,)=q02。,2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,18,从RE到FA的等价变换(cont.),构造RE r=r1*对应的FA设r1M1=Q1,1,q01,qf1；取q0,qfQ1，令M=(Q1q0,qf,q0,qf)定义 qQ1-f1,a,(q,a)=1(q,a);(qf1,)=q01,qf;(q0,)=q01,qf;,2023/8/19,Guohong Fu,School of Computer Sci&
14、Tech,HLJU,19,从RE到FA的等价变换(cont.),简单的例子RE 0对应的FARE 01对应的FARE 0+1对应的FARE 0*对应的FA,q0,1,S,q1,q0,0,S,q2,q1,1,2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,20,从RE到FA的等价变换(cont.),例 4-3 构造与(0+1)*0+(00)*等价的FA。,(1)构造与0等价的-NFA M1;,(2)构造与1等价的-NFA M2;,(3)构造与0+1等价的-NFA M3;,(4)构造与(0+1)*等价的-NFA M4;,(5)构造与(0+
15、1)*0等价的-NFA M5;,(6)构造与00等价的-NFA M6;,(7)构造与(00)*等价的-NFA M7;,(8)构造与(0+1)*0+(00)*等价的-NFA M8;,2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,21,从RE到FA的等价变换(cont.),定义4-4 正则表达式r称为与FA M等价，如果L(r)=L(M)定理 4-1 RE表示的语言是RL证明：思想施归纳于正则表达式中所含的运算符的个数n，证明对于字母表上的任意正则表达式r，存在FA M，使得L(M)=L(r)；对于一个给定的正则表达式，按照正则表达式的
16、递归定义构造相应的FA；,2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,22,从RE到FA的等价变换(cont.),当n=0时，由RE定义有三种情形,(1)r=，以下NFA满足要求，都表示语言；,(2)r=，以下NFA满足要求，都表示语言；,(3)r=a，以下NFA满足要求，都表示语言a；,2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,23,从RE到FA的等价变换(cont.),设n=k时结论成立此时有如下FAM1=(Q1,1,q01,qf1)M2=(Q2,2,q02,q
17、f2)Q1Q2=L(M1)=L(r1)L(M2)=L(r2),2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,24,从RE到FA的等价变换(cont.),当n=k+1时 根据RE定义，考虑三种情形加：r=r1+r2乘：r=r1r2闭包：r=r1*分别(1)构造等价的FA(2)等价性证明Ref.教材pp.136-143,2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,25,从DFA到RE的等价变换,三种方法(1)计算等价类的方法(2)计算qi到qj的字符串集合Rkij的方法(3
18、)图上作业法,2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,26,从DFA构造RE：等价类的方法,基本思想(1)逐个计算DFA每个状态对应的字符串的集合，即字母表的克林闭包的等价分类；(2)用RE表示每个终止状态所对应的字符串的集合；(3)将得到的RE加起来即可得到DFA对应的RE。,2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,27,从DFA构造RE：等价类的方法(cont.),例：将下图所示的DFA转换成RE,(1)计算每个状态对应的字符串集,set(q0)=1n|n
19、0=1*,set(q1)=set(q0)00,1*=1*00,1*,(2)用RE表示每个终止状态对应的字符串集,r=1*0(0+1)*,注意：容易出错，难以自动化,2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,28,从DFA构造RE：计算Rkij的方法,基本思想设DFA M=(q1,q2,qn,q1,F)，令Rkij=x|(qi,x)=qj,且对于x的任意前缀y(yx,y),如果(qi,y)=qh,则hk表示所有将DFA从给定状态qi引导到状态qj，并且“途中”不经过(进入或离开)下标大于k的状态的所有字符串。为方便计算Rkij可递
20、归地定义为：显然 L(M)=qfFRn1f,Rkij=Rk-1ik(Rk-1kk)*Rk-1kjRk-1ij,2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,29,从DFA构造RE：计算Rkij的方法(cont.),根据Rkij的递归计算可递归地求出对应的RE当R0ij=时，对应的RE为；当R0ij=a1,a2,al时，对应的RE为a1+a2+al;仅当i=j时，集合R0ij中含有；Rkij中含有的都是RE使用的运算，因此很容易可以得到Rkij对应的RE,2023/8/19,Guohong Fu,School of Computer
21、Sci&Tech,HLJU,30,从DFA构造RE：计算Rkij的方法(cont.),例：将下图所示的DFA转换成RE,(1)计算R0ij,2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,31,从DFA构造RE：计算Rkij的方法(cont.),(2)计算R1ij,R1ij=R0i1(R011)*R01j+R0ij,R0ij,2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,32,从DFA构造RE：计算Rkij的方法(cont.),(3)计算R2ijR212即为所求即：该DFA
22、对应的RE为1*0(0+1)*,R2ij=R1i2(R122)*R12j+R1ij,R1ij,2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,33,从DFA构造RE：图上作业法,启示,2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,34,从DFA构造RE：图上作业法(cont.),图上作业法操作步骤(1)预处理：用标记为X和Y的状态将M“括起来”：在状态转移图中增加标记为X和Y的状态；从标记为X的状态到标记为q0的状态引一条标记为的弧；从标记为q(qF)的状态到标记为Y的状态
23、分别引一条标记为的弧。去掉所有的不可达状态；,2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,35,从DFA构造RE：图上作业法(cont.),(2)对通过步骤(1)处理所得到的状态转移图重复如下操作，直到该图中不再包含除了标记为X和Y外的其他状态，并且这两个状态之间最多只有一条弧并弧：将从q到p的标记为r1，r2，rg并行弧用从q到p的、标记为r1+r2+rg的弧取代这g个并行弧；去状态1如果从q到p有一条标记为r1的弧，从p到t有一条标记为r2的弧，不存在从状态p到状态p的弧，将状态p和与之关联的这两条弧去掉，用一条从q到t的标记
24、为r1r2的弧代替；去状态2如果从q到p有一条标记为r1的弧，从p到t有一条标记为r2的弧，从状态p到状态p标记为r3的弧，将状态p和与之关联的这三条弧去掉，用一条从q到t的标记为r1r3*r2的弧代替；,2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,36,从DFA构造RE：图上作业法(cont.),去状态3如果图中只有三个状态，而且不存在从标记为X的状态到达标记为Y的状态的路，则将除标记为X的状态和标记为Y的状态之外的第3个状态及其相关的弧全部删除；(3)从标记为X的状态到标记为Y的状态的弧的标记为所求的正则表达式。如果此弧不存在
25、，则所求的正则表达式为；,2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,37,从DFA构造RE：图上作业法(cont.),例 4-4 求图4-14所示的DFA等价的RE,2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,38,从DFA构造RE：图上作业法(cont.),预处理,q1,0,S,q0,q2,0,q3,0,1,q4,1,1,0,1,X,Y,q3,q4,2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,39,从
26、DFA构造RE：图上作业法(cont.),去掉状态q3,q1,0,q0,q2,0,0,1,1,1,0,1,X,Y,q3,q4,00*,00*1,2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,40,从DFA构造RE：图上作业法(cont.),去掉状态q4,q1,0,q0,q2,0,1,1,0,1,X,Y,q4,00*,00*1,00*1,00*10,00*11,2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,41,从DFA构造RE：图上作业法(cont.),合并从标记为q2的
27、状态到标记为Y的状态的两条并行弧,q1,0,q0,q2,0,1,1,X,Y,00*,00*1,00*10,00*11,+00*1,2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,42,从DFA构造RE：图上作业法(cont.),去掉状态q0,q1,0,q0,q2,0,1,1,X,Y,00*,11*0,00*11,+00*1,1*0,00*111*0,00*10,2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,43,从DFA构造RE：图上作业法(cont.),q2到q1的并弧,
28、q1,0,q2,X,Y,00*,11*0,+00*1,1*0,00*111*0,00*10,+11*0,+00*10,2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,44,从DFA构造RE：图上作业法(cont.),去掉q1,q1,0,q2,X,Y,00*,+00*1,1*0,00*111*0,+11*0,+00*10,1*011*00,(00*111*0+11*0+00*10)11*00,2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,45,从DFA构造RE：图上作业法(c
29、ont.),去掉q2,q2,X,Y,00*,+00*1,1*011*00,(00*111*0+11*0+00*10)11*00,1*011*00,(00*111*0+11*0+00*10)11*00,(00*+00*1),2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,46,从DFA构造RE：图上作业法(cont.),几点值得注意的问题(1)如果去状态的顺序不一样，则得到的RE可能在形式是不一样，但它们都是等价的；(2)当DFA的终止状态都是不可达的时候，状态转移图中必不存在从开始状态到终止状态的路。此时，相应的RE为；(3)不计算自
30、身到自身的弧，如果状态q的入度为n，出度为m，则将状态q及其相关的弧去掉之后，需要添加n*m条新弧；(4)对操作的步数施归纳，可以证明它的正确性。,2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,47,从DFA到RE的等价转换,定理4-2 RL可以用RE表示。推论4-1 正则表达式与FA、正则文法等价，是正则语言的表示模型。,2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,48,正则语言等价模型的总结,AaB B(A,a)Aa qf(A,a),RG,DFA,NFA,RE,-N
31、FA,DFA(P,a)=NFA(P,a),归纳法,图上作业法,(q,a)=pqap(q,a)=pF qa,NFA(q,a)=-NFA(q,a),2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,49,4.5 小结,本章讨论了RL及其与FA的等价性。(1)字母表上的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等价。(2)RE的运算定律乘、加满足结合律；乘对加满足左、右分配律；加满
32、足交换率和幂等率；是加运算和乘运算的零元素；是乘运算的单位元；,2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,50,4.5 小结(cont.),(3)RE是RL的一种描述容易根据RE构造出与它等价的FA；反过来，可以用图上作业法构造出与给定的DFA等价的RE。(4)RL的5种等价描述模型转换图。,2023/8/19,Guohong Fu,School of Computer Sci&Tech,HLJU,51,课后阅读和作业,必读蒋宗礼,姜守旭.形式语言与自动机理论.北京：清华大学出版社,2003.pp.131-152参考John E.Hopcroft,Rajeev Motwani,Jeffrey D.Ullman 著，刘田等译.自动机理论、语言和计算导论.机械工业出版社，中信出版社，2005.pp.57-81作业 6教材：pp.153-155 习题1(5),2(2),5(2),6(图4-24)上交时间：2008-10-30 星期四,
