正则表达式教学.ppt

《正则表达式教学.ppt》由会员分享，可在线阅读，更多相关《正则表达式教学.ppt（51页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第四章第四章 正则表达式正则表达式付国宏付国宏黑龙江大学计算机科学技术学院黑龙江大学计算机科学技术学院形式语言与自动机理论形式语言与自动机理论2022/12/121Guohong Fu,School of Computer Sci&Tech,HLJU引言引言 RG擅长语言的产生；擅长语言的产生；FA擅长语言的识别；擅长语言的识别；正则表达式正则表达式-正则语言的代数表示正则语言的代数表示在对正则语言的表达上具有特殊的优势；在对正则语言的表达上具有特殊的优势；简洁、更接近语言的集合表示和语言的计算简洁、更接近语言的集合表示和语言的计算机表示等；机表示等；为正则语言的计算机处理提供了方便条件。为正

2、则语言的计算机处理提供了方便条件。2022/12/122Guohong Fu,School of Computer Sci&Tech,HLJU提要提要主要内容主要内容RE的非形式化描述和形式定义的非形式化描述和形式定义典型典型RE的构造的构造与与RE等价等价FA的构造方法的构造方法与与DFA等价的等价的RE的构造的构造重点重点RE的概念的概念RE与与DFA的等价性的等价性难点难点RE与与DFA的等价性证明的等价性证明 2022/12/123Guohong Fu,School of Computer Sci&Tech,HLJURE的非形式化描述的非形式化描述 基本思想：基本思想：用代数的方法表示

3、正规语言用代数的方法表示正规语言语义：作用于语言上的三种代数运算语义：作用于语言上的三种代数运算两个语言两个语言L1和和L2的并，记作的并，记作L1 L2L1 L2=w w L1或或 w L2 设设L1=001,10,L2=,001，则，则L1 L2=,001,10两个语言两个语言L1和和L2的连接，记作的连接，记作L1 L2 或或L1L2 L1 L2=w1w2 w1 L1 且且 w2 L2 L1L2=001,10,001=001,001001,10,10001语言语言L的的(星或克林星或克林)闭包，记作闭包，记作L*L*=L0 L1 L2 =i 0 Li，其中，其中，L0=，L1=L,L2=

4、LL,Li=Li-1L,L=0,1，则，则L*表示所有的表示所有的0和和1的串的串L=0,11，则，则L*表示使表示使1成对出现的所有的成对出现的所有的0和和1的串的串2022/12/124Guohong Fu,School of Computer Sci&Tech,HLJURE的形式定义的形式定义 正则表达式正则表达式(regular expression，RE)(1)是是 上的上的RE，它表示语言，它表示语言；(2)是是 上的上的RE，它表示语言，它表示语言；(3)对于对于 a ，a是是上的上的RE，它表示语言，它表示语言a；(4)如如果果r和和s分分别别是是 上上表表示示语语言言L(r)

5、和和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。2022/12/125Guohong Fu,Sc

6、hool of Computer Sci&Tech,HLJURE的形式定义的形式定义(cont.)例例 4-1 设设=0,1(1)0-表示语言表示语言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)-

7、表示所有以表示所有以01结尾的结尾的0、1字符串组成的语言；字符串组成的语言；(10)(1(0+1)*)0)-表表示示所所有有以以1开开头头，并并且且以以0结结尾尾的的0、1字字符串组成的语言。符串组成的语言。利用利用RE的定义理解的定义理解RE表示的语言表示的语言2022/12/126Guohong Fu,School of Computer Sci&Tech,HLJURE的形式定义的形式定义(cont.)RE运算符的优先级运算符的优先级闭包运算的优先级最高闭包运算的优先级最高乘运算乘运算“”的优先级次之的优先级次之加运算加运算“+”的优先级最低的优先级最低在意义明确时，可以省略其中某些括号

8、在意义明确时，可以省略其中某些括号(0+1)*)000)(0+1)*)=(0+1)*000(0+1)*(0+1)*)(0+1)(0+1)*)=(0+1)*(0+1)(0+1)*2022/12/127Guohong Fu,School of Computer Sci&Tech,HLJURE的形式定义的形式定义(cont.)约定约定 用用r的正闭包的正闭包r+表示表示r与与(r*)的乘积以及的乘积以及(r*)与与r的乘积：的乘积：r+=rr*=r*r在意义明确时，在意义明确时，RE r表示的语言记为表示的语言记为L(r)，也可直，也可直接记为接记为r；加、乘、闭包运算均执行左结合规则；加、乘、闭包

9、运算均执行左结合规则；2022/12/128Guohong Fu,School of Computer Sci&Tech,HLJURE的形式定义的形式定义(cont.)相等相等(equivalence)设设r、s是字母表是字母表 上的一个上的一个RE，如果如果L(r)=L(s)，则称，则称r与与s相等，相等，记作记作r=s；相等也称为相等也称为等价。等价。2022/12/129Guohong Fu,School of Computer Sci&Tech,HLJURE的形式定义的形式定义(cont.)幂幂 r是字母表是字母表上的上的RERE，r的的n次次幂幂定义为定义为 r0=；rn=rn-1r

10、，n 1 2022/12/1210Guohong Fu,School of Computer Sci&Tech,HLJURE的形式定义的形式定义(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;2022/

11、12/1211Guohong Fu,School of Computer Sci&Tech,HLJU4.2 RE的形式定义的形式定义(cont.)(11)L(rs)=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，rs sr2022/12/121

12、2Guohong Fu,School of Computer Sci&Tech,HLJURE的形式定义的形式定义(cont.)例例 4-2 设设=0,100表示语言表示语言00；(0+1)*00(0+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,k 1；L(0*1*2*)=0n1m2k|m,n,k 0；L(1(0+1)*1+0(

13、0+1)*0)=x|x的开头字符与尾字符相同的开头字符与尾字符相同。利用利用RE的运算律理解的运算律理解RE表示的语言表示的语言2022/12/1213Guohong Fu,School of Computer Sci&Tech,HLJURE与与FA的等价变换的等价变换AaB B(A,a)Aa qf(A,a)RGDFANFARE-NFA DFA(P,a)=NFA(P,a)归纳法归纳法图上作业法图上作业法(q,a)=pqap(q,a)=p F qa NFA(q,a)=-NFA(q,a)RL相关模型之间的等价构造关系相关模型之间的等价构造关系2022/12/1214Guohong Fu,Schoo

14、l of Computer Sci&Tech,HLJU从从RE构造构造FA的等价变换的等价变换归纳法：归纳法：根据根据RE的递归定义构造相应的的递归定义构造相应的FA(-NFA)(1)基础基础RE r=对应的对应的FARE r=对应的对应的FARE r=a对应的对应的FAq0Sqfq0Sqfq0aSqf2022/12/1215Guohong Fu,School of Computer Sci&Tech,HLJU从从RE到到FA的等价变换的等价变换(cont.)(2)归纳归纳构造构造RE r=r1+r2对应的对应的FA设设r1 M1=Q1,1,q01,qf1,r2 M2=Q2,2,q02,qf2

15、；取取q0，qf Q1Q2，令，令 M=(Q1Q2q0,qf,q0,qf)(q0,)=q01,q02;q Q1,a,(q,a)=1(q,a);qQ2,a,(q,a)=2(q,a);(qf1,)=qf,(qf2,)=qf。q01M1Sqfq02M2qf1qf2q0 2022/12/1216Guohong Fu,School of Computer Sci&Tech,HLJU从从RE到到FA的等价变换的等价变换(cont.)构造构造RE r=r1 r2对应的对应的FA设设r1 M1=Q1,1,q01,qf1,r1 M2=Q2,2,q02,qf2；取取M=(Q1Q2,q01,qf2)定义定义 q Q

16、1-qf1,a,(q,a)=1(q,a);q Q2-qf2,a,(q,a)=2(q,a);(qf1,)=q02。q01M1Sq02M2qf1 qf22022/12/1217Guohong Fu,School of Computer Sci&Tech,HLJU从从RE到到FA的等价变换的等价变换(cont.)构造构造RE r=r1*对应的对应的FA设设r1 M1=Q1,1,q01,qf1；取取q0,qf Q1，令M=(Q1q0,qf,q0,qf)定义定义 q Q1-f1,a,(q,a)=1(q,a);(qf1,)=q01,qf;(q0,)=q01,qf;q01M1Sq0qf1 qf 2022/1

17、2/1218Guohong Fu,School of Computer Sci&Tech,HLJU从从RE到到FA的等价变换的等价变换(cont.)简单的例子简单的例子RE 0对应的对应的FARE 01对应的对应的FARE 0+1对应的对应的FARE 0*对应的对应的FAq01Sq1q00Sq2q11q10Sq5q31q2q4q0 q10Sq0q2 q3 2022/12/1219Guohong Fu,School of Computer Sci&Tech,HLJU从从RE到到FA的等价变换的等价变换(cont.)例例 4-3 构造与构造与 (0+1)*0+(00)*等价的等价的FA。010S0

18、0(1)构造与0等价的-NFA M1;(2)构造与1等价的-NFA M2;(3)构造与0+1等价的-NFA M3;(4)构造与(0+1)*等价的-NFA M4;(5)构造与(0+1)*0等价的-NFA M5;(6)构造与00等价的-NFA M6;(7)构造与(00)*等价的-NFA M7;(8)构造与(0+1)*0+(00)*等价的-NFA M8;2022/12/1220Guohong Fu,School of Computer Sci&Tech,HLJU从从RE到到FA的等价变换的等价变换(cont.)定义定义4-44-4 正则表达式正则表达式r称为与称为与FA M等价，如果等价，如果L(r

19、)=L(M)定理定理 4-1 RE表示的语言是表示的语言是RL证明：证明：思想思想施归纳于正则表达式中所含的运算符的个数施归纳于正则表达式中所含的运算符的个数n，证，证明对于字母表明对于字母表上的任意正则表达式上的任意正则表达式r，存在，存在FA M，使得，使得L(M)=L(r)；对于一个给定的正则表达式，按照正则表达式的递对于一个给定的正则表达式，按照正则表达式的递归定义构造相应的归定义构造相应的FA；2022/12/1221Guohong Fu,School of Computer Sci&Tech,HLJU从从RE到到FA的等价变换的等价变换(cont.)当当n=0时，由时，由RE定义有

20、三种情形定义有三种情形(1)r=，以下，以下NFA满足要求，满足要求，都表示语言都表示语言；(2)r=，以下，以下NFA满足要求，满足要求，都表示语言都表示语言；q0qfS(3)r=a，以下，以下NFA满足要求，满足要求，都表示语言都表示语言a；q0qfSq0aqfS2022/12/1222Guohong Fu,School of Computer Sci&Tech,HLJU从从RE到到FA的等价变换的等价变换(cont.)设设n=k时结论成立时结论成立此时有如下此时有如下FAM1=(Q1,1,q01,qf1)M2=(Q2,2,q02,qf2)Q1Q2=L(M1)=L(r1)L(M2)=L(r

21、2)2022/12/1223Guohong Fu,School of Computer Sci&Tech,HLJU从从RE到到FA的等价变换的等价变换(cont.)当当n=k+1时时 根据根据RE定义，考虑三种情形定义，考虑三种情形加：加：r=r1+r2乘：乘：r=r1r2闭包：闭包：r=r1*分别分别(1)构造等价的构造等价的FA(2)等价性证明等价性证明Ref.教材教材pp.136-1432022/12/1224Guohong Fu,School of Computer Sci&Tech,HLJU从从DFA到到RE的等价变换的等价变换 三种方法三种方法(1)计算等价类的方法计算等价类的方法

22、(2)计算计算qi到到qj的字符串集合的字符串集合Rkij的方法的方法(3)图上作业法图上作业法2022/12/1225Guohong Fu,School of Computer Sci&Tech,HLJU从从DFA构造构造RE：等价类的方法：等价类的方法基本思想基本思想(1)逐个计算逐个计算DFA每个状态对应的字符串的集合，即每个状态对应的字符串的集合，即字母表的克林闭包的等价分类；字母表的克林闭包的等价分类；(2)用用RE表示每个终止状态所对应的字符串的集合；表示每个终止状态所对应的字符串的集合；(3)将得到的将得到的RE加起来即可得到加起来即可得到DFA对应的对应的RE。2022/12/

23、1226Guohong Fu,School of Computer Sci&Tech,HLJU从从DFA构造构造RE：等价类的方法：等价类的方法(cont.)例：将下图所示的例：将下图所示的DFA转换成转换成RESq0q100,11(1)计算每个状态对应的字符串集计算每个状态对应的字符串集set(q0)=1n|n 0=1*set(q1)=set(q0)00,1*=1*00,1*(2)用用RE表示每个终止状态对应的字符串集表示每个终止状态对应的字符串集r=1*0(0+1)*注意：容易出错，难以自动化注意：容易出错，难以自动化2022/12/1227Guohong Fu,School of Com

24、puter Sci&Tech,HLJU从从DFA构造构造RE：计算计算Rkij的方法的方法基本思想基本思想设设DFA M=(q1,q2,qn,q1,F)，令令Rkij=x|(qi,x)=qj,且对于且对于x的任意前缀的任意前缀y(y x,y),如果如果(qi,y)=qh,则则h k表示所有将表示所有将DFA从给定状态从给定状态qi引导到状态引导到状态qj，并且，并且“途中途中”不经不经过过(进入或离开进入或离开)下标大于下标大于k的状态的所有字符串。的状态的所有字符串。为方便计算为方便计算Rkij可递归地定义为：可递归地定义为：显然显然 L(M)=qf FRn1fa|(qi,a)=qj,if

25、i jR0ij=a|(qi,a)=qj ,if i=jRkij=Rk-1ik(Rk-1kk)*Rk-1kj Rk-1ij2022/12/1228Guohong Fu,School of Computer Sci&Tech,HLJU从从DFA构造构造RE：计算计算Rkij的方法的方法(cont.)根据根据Rkij的递归计算的递归计算可递归地求出对应的可递归地求出对应的RE当当R0ij=时，对应的时，对应的RE为为；当当R0ij=a1,a2,al时，对应的时，对应的RE为为a1+a2+al;仅当仅当i=j时，集合时，集合R0ij中含有中含有；Rkij中含有的都是中含有的都是RE使用的运算，因此很容

26、易可以使用的运算，因此很容易可以得到得到Rkij对应的对应的RE2022/12/1229Guohong Fu,School of Computer Sci&Tech,HLJU从从DFA构造构造RE：计算计算Rkij的方法的方法(cont.)例：将下图所示的例：将下图所示的DFA转换成转换成RESq0q100,11(1)计算计算R0ijR011 1+1R01200R021R022 0,1+0+1a|(qi,a)=qj,if i jR0ij=a|(qi,a)=qj ,if i=j2022/12/1230Guohong Fu,School of Computer Sci&Tech,HLJU从从DFA

27、构造构造RE：计算计算Rkij的方法的方法(cont.)(2)计算计算R1ijR011+1R0120R021R022+0+1R1ij=R0i1(R011)*R01j+R0ijR0ijR111(+1)(+1)*(+1)+(+1)1*R112(+1)(+1)*0+01*0R121(+1)*(+1)+R122(+1)*0+0+1+0+12022/12/1231Guohong Fu,School of Computer Sci&Tech,HLJU从从DFA构造构造RE：计算计算Rkij的方法的方法(cont.)(3)计算计算R2ijR212即为所求即为所求即：该即：该DFA对应的对应的RE为为1*0(

28、0+1)*R2ij=R1i2(R122)*R12j+R1ijR2111*0(+0+1)*+1*1*R2121*0(+0+1)*(+0+1)+1*01*0(0+1)*R221(+0+1)(+0+1)*+R222(+0+1)(+0+1)*(+0+1)+(+0+1)(0+1)*R1111*R1121*0R121R122+0+1R1ij2022/12/1232Guohong Fu,School of Computer Sci&Tech,HLJU从从DFA构造构造RE：图上作业法：图上作业法启示启示2022/12/1233Guohong Fu,School of Computer Sci&Tech,HL

29、JU从从DFA构造构造RE：图上作业法：图上作业法(cont.)图上作业法操作步骤图上作业法操作步骤(1)预处理：预处理：用标记为用标记为X和和Y的状态将的状态将M“括起来括起来”：在状态转移图中增加标记为在状态转移图中增加标记为X和和Y的状态；的状态；从从标标记记为为X的的状状态态到到标标记记为为q0的的状状态态引引一一条条标标记记为为的的弧；弧；从从标标记记为为q(qF)的的状状态态到到标标记记为为Y的的状状态态分分别别引引一一条条标记为标记为的弧。的弧。去掉所有的不可达状态；去掉所有的不可达状态；2022/12/1234Guohong Fu,School of Computer Sci&

30、Tech,HLJU从从DFA构造构造RE：图上作业法：图上作业法(cont.)(2)对对通通过过步步骤骤(1)处处理理所所得得到到的的状状态态转转移移图图重重复复如如下下操操作作，直直到到该该图图中中不不再再包包含含除除了了标标记记为为X和和Y外外的的其其他状态，并且这两个状态之间最多只有一条弧他状态，并且这两个状态之间最多只有一条弧并弧：并弧：将将从从q到到p的的标标记记为为r1，r2，rg并并行行弧弧用用从从q到到p的的、标标记记为为r1+r2+rg的弧取代这的弧取代这g个并行弧；个并行弧；去状态去状态1 1如如果果从从q到到p有有一一条条标标记记为为r1的的弧弧，从从p到到t有有一一条条

31、标标记记为为r2的的弧弧，不不存存在在从从状状态态p到到状状态态p的的弧弧，将将状状态态p和和与与之之关关联联的的这这两条弧去掉，用一条从两条弧去掉，用一条从q到到t的标记为的标记为r1r2的弧代替；的弧代替；去状态去状态2 2如如果果从从q q到到p p有有一一条条标标记记为为r r1 1的的弧弧，从从p p到到t t有有一一条条标标记记为为r r2 2的的弧弧，从从状状态态p p到到状状态态p p标标记记为为r r3 3的的弧弧，将将状状态态p p和和与与之之关关联联的的这三条弧去掉，用一条从这三条弧去掉，用一条从q q到到t t的标记为的标记为r r1 1r r3 3*r r2 2的弧代

32、替；的弧代替；2022/12/1235Guohong Fu,School of Computer Sci&Tech,HLJU从从DFA构造构造RE：图上作业法：图上作业法(cont.)去状态去状态3 3如如果果图图中中只只有有三三个个状状态态，而而且且不不存存在在从从标标记记为为X的的状状态态到到达达标标记记为为Y的的状状态态的的路路，则则将将除除标标记记为为X的的状状态态和和标标记记为为Y的的状状态态之之外外的的第第3个个状状态态及及其其相相关关的的弧弧全全部部删删除；除；(3)(3)从从标标记记为为X的的状状态态到到标标记记为为Y的的状状态态的的弧弧的标记为所求的正则表达式。的标记为所求的

33、正则表达式。如果此弧不存在，则所求的正则表达式为如果此弧不存在，则所求的正则表达式为；2022/12/1236Guohong Fu,School of Computer Sci&Tech,HLJU从从DFA构造构造RE：图上作业法：图上作业法(cont.)例例 4-4 求图求图4-14所示的所示的DFA等价的等价的REq10Sq0q20q301q41101012022/12/1237Guohong Fu,School of Computer Sci&Tech,HLJU从从DFA构造构造RE：图上作业法：图上作业法(cont.)预处理预处理q10Sq0q20q301q4110101XYq3q4

34、2022/12/1238Guohong Fu,School of Computer Sci&Tech,HLJU从从DFA构造构造RE：图上作业法：图上作业法(cont.)去掉状态去掉状态q3q10q0q2001110101XYq3q4 0000*0000*1 12022/12/1239Guohong Fu,School of Computer Sci&Tech,HLJU从从DFA构造构造RE：图上作业法：图上作业法(cont.)去掉状态去掉状态q4q10q0q2011011XYq4 0000*0000*1 10000*1 10000*10100000*11112022/12/1240Guoho

35、ng Fu,School of Computer Sci&Tech,HLJU从从DFA构造构造RE：图上作业法：图上作业法(cont.)合合并并从从标标记记为为q2的的状状态态到到标标记记为为Y的的状状态态的的两两条并行弧条并行弧q10q0q20111XY 0000*0000*1 10000*10100000*1111+00+00*1 12022/12/1241Guohong Fu,School of Computer Sci&Tech,HLJU从从DFA构造构造RE：图上作业法：图上作业法(cont.)去掉状态去掉状态q0q10q0q20111XY 0000*1111*0 00000*111

36、1+00+00*1 11 1*0 01111*0 00000*111111*0 00000*10102022/12/1242Guohong Fu,School of Computer Sci&Tech,HLJU从从DFA构造构造RE：图上作业法：图上作业法(cont.)q2到到q1的并弧的并弧q10q2XY0000*1111*0 0+00+00*1 11 1*0 01111*0 00000*111111*0 00000*1010+11+11*0 0+00+00*10102022/12/1243Guohong Fu,School of Computer Sci&Tech,HLJU从从DFA构造构

37、造RE：图上作业法：图上作业法(cont.)去掉去掉q1q10q2XY0000*+00+00*1 11 1*0 01111*0 00000*111111*0 0+11+11*0 0+00+00*10101 1*011011*0000(00(00*111111*0+110+11*0+000+00*10)1110)11*00002022/12/1244Guohong Fu,School of Computer Sci&Tech,HLJU从从DFA构造构造RE：图上作业法：图上作业法(cont.)去掉去掉q2q2XY0000*+00+00*1 11 1*011011*0000(00(00*11111

38、1*0+110+11*0+000+00*10)1110)11*00001 1*011011*0000(00(00*111111*0+110+11*0+000+00*10)1110)11*0000(00(00*+00+00*1)1)2022/12/1245Guohong Fu,School of Computer Sci&Tech,HLJU从从DFA构造构造RE：图上作业法：图上作业法(cont.)几点值得注意的问题几点值得注意的问题(1)如果去状态的顺序不一样，则得到的如果去状态的顺序不一样，则得到的RE可能在形可能在形式是不一样，但它们都是等价的；式是不一样，但它们都是等价的；(2)当当DF

39、A的终止状态都是不可达的时候，状态转移图的终止状态都是不可达的时候，状态转移图中必不存在从开始状态到终止状态的路。此时，相中必不存在从开始状态到终止状态的路。此时，相应的应的RE为为；(3)不计算自身到自身的弧，如果状态不计算自身到自身的弧，如果状态q的入度为的入度为n，出度为出度为m，则将状态，则将状态q及其相关的弧去掉之后，需要及其相关的弧去掉之后，需要添加添加n*m条新弧；条新弧；(4)对操作的步数施归纳，可以证明它的正确性。对操作的步数施归纳，可以证明它的正确性。2022/12/1246Guohong Fu,School of Computer Sci&Tech,HLJU从从DFA到到

40、RE的等价转换的等价转换定理定理4-2 RL可以用可以用RE表示。表示。推论推论4-1 正则表达式与正则表达式与FA、正则文法等价，是正、正则文法等价，是正则语言的表示模型。则语言的表示模型。2022/12/1247Guohong Fu,School of Computer Sci&Tech,HLJU正则语言等价模型的总结正则语言等价模型的总结 AaB B(A,a)Aa qf(A,a)RGDFANFARE-NFA DFA(P,a)=NFA(P,a)归纳法归纳法图上作业法图上作业法(q,a)=pqap(q,a)=p F qa NFA(q,a)=-NFA(q,a)2022/12/1248Guoho

41、ng Fu,School of Computer Sci&Tech,HLJU4.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的运算定律的运算定律乘、加满足结合律；乘、加满足结合律；乘对加满足左、右分

42、配律；乘对加满足左、右分配律；加满足交换率和幂等率；加满足交换率和幂等率；是加运算和乘运算的零元素；是加运算和乘运算的零元素；是乘运算的单位元；是乘运算的单位元；2022/12/1249Guohong Fu,School of Computer Sci&Tech,HLJU4.5 小结小结(cont.)(3)RE是是RL的一种描述的一种描述容易根据容易根据RE构造出与它等价的构造出与它等价的FA；反反过过来来，可可以以用用图图上上作作业业法法构构造造出出与与给给定定的的DFA等等价的价的RE。(4)RL的的5种等价描述模型转换图。种等价描述模型转换图。2022/12/1250Guohong Fu

43、,School of Computer Sci&Tech,HLJU课后阅读和作业必读必读蒋宗礼蒋宗礼,姜守旭姜守旭.形式语言与自动机理论形式语言与自动机理论.北京：清北京：清华大学出版社华大学出版社,2003.pp.131-152pp.131-152 参考参考John E.Hopcroft,Rajeev Motwani,Jeffrey D.Ullman 著，刘田等译著，刘田等译.自动机理论、语言和计算导自动机理论、语言和计算导论论.机械工业出版社，中信出版社，机械工业出版社，中信出版社，2005.pp.57-pp.57-8181作业作业 6教材：教材：pp.153-155 pp.153-155 习题习题1(5),2(2),5(2),6(1(5),2(2),5(2),6(图图4-244-24)上交时间：上交时间：2008-10-30 2008-10-30 星期四星期四2022/12/1251Guohong Fu,School of Computer Sci&Tech,HLJU