《形式语言与自动机理论--第四章 正则表达式（第十周）》由会员分享，可在线阅读，更多相关《形式语言与自动机理论--第四章 正则表达式（第十周）（61页珍藏版）》请在金锄头文库上搜索。
1、第第4章章 正则表达式正则表达式 1.1.正则表达式的引出正则表达式的引出2.2.正则表达式的形式定义正则表达式的形式定义3.3.正则表达式与正则表达式与FAFA等价等价4.4.正则语言等价模型总结正则语言等价模型总结5.5.小结小结11.正则表达式的引出正则表达式的引出产生语言产生语言anbmck|n，m，k1aicnbxam|i0, ,n1, ,m2, ,x为为d和和e组成的串组成的串的正则文法为的正则文法为AaA|aB|cEBbB|bCCcC|cE cE|bFFdF|eF|aHHaH|a21.正则表达式的引出正则表达式的引出接受此语言的接受此语言的NFA M31.正则表达式的引出正则表达
2、式的引出计算集合计算集合set(q)set(A)=an|n0=a* set(B)= set(A)abn|n0 =anabm|m，n0 =a*ab*=a+b*set(C)= set(B)bc* =a*ab*bc*=a+b+c*set(D)= set(C) c=a+b+c*c =a+b+c+41.正则表达式的引出正则表达式的引出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+d，e*aa* =a*c+d，e*a+set(I)= set(H)a=a*c+d，e*a+aL(M)= set(D
3、)set(I) = a+b+c+a*c+d，e*a+a51.正则表达式的引出正则表达式的引出根据集合运算的定义，根据集合运算的定义，d，e=de。从而，从而，d，e*=(de)*。这样可以将这样可以将L(M)写成如下形式：写成如下形式：L(M)= a+b+c+a*c+(de)*a+a记作：记作：a+b+c+a*c+(d+e)*a+a= aa*bb*cc*+a*cc*(d+e)* aaa*62.RE的形式定义的形式定义定义定义4-1：正则表达式：正则表达式(regularexpression，RE) 是是上的上的RE，它表示语言，它表示语言； 是是上的上的RE，它表示语言，它表示语言； 对于对于
4、 a，a是是上的上的RE，它表示语言，它表示语言a；72.RE的形式定义的形式定义 如果如果r和和s分别是分别是上表示语言上表示语言R和和S的的RE，则：，则： r与与s的的“和和” (r+s)是是上上的的RE，(r+s)表表达达的的语语言言为为RS； r与与s的的“乘乘积积” (rs)是是上上的的RE，(rs)表表达达的的语语言言为为RS； r的克林闭包的克林闭包(r*)是是上的上的RE，(r*)表达的语言为表达的语言为R*。 只有满足只有满足、的才是的才是上的上的RE。82.RE的形式定义的形式定义例例4-1 设设=0，1 0，表示语言，表示语言0； 1，表示语言，表示语言1； (0+1)
5、，表示语言，表示语言0，1； (01)，表示语言，表示语言01； (0+1)*)，表示语言，表示语言0，1*； (00)(00)*)，表示语言，表示语言0000*；92.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字符串组成的语言
6、。字符串组成的语言。102.RE的形式定义的形式定义约定约定 r的正闭包的正闭包r+表示表示r与与(r*)的乘积以及的乘积以及(r*)与与r的乘积：的乘积： r+=(r(r*)=(r*)r) 闭包运算的优先级最高，乘运算的优先级次之，闭包运算的优先级最高，乘运算的优先级次之，加运算加运算“+”的优先级最低。所以，在意义明确时，的优先级最低。所以，在意义明确时，可以省略其中某些括号。可以省略其中某些括号。(0+1)*)000)(0+1)*)=(0+1)*000(0+1)*112.RE的形式定义的形式定义(0+1)*)(0+1)(0+1)*)=(0+1)*(0+1)(0+1)* 在在意意义义明明确
7、确时时，RE r表表示示的的语语言言记记为为L(r)，也也可可以直接地记为以直接地记为r。 加、乘、闭包运算均执行左结合规则。加、乘、闭包运算均执行左结合规则。122.RE的形式定义的形式定义定义定义4-2：正则表达式相等：正则表达式相等(equivalence)r、s是字母表是字母表上的一个上的一个RE，如果，如果L(r)=L(s)，则称，则称r与与s相等，相等，记作记作r=s。相等也称为相等也称为等价。等价。几个基本结论几个基本结论结合律：结合律：(rs)t=r(st)(r+s)+t=r+(s+t)分配律：分配律：r(s+t)=rs+rt(s+t)r=sr+tr132.RE的形式定义的形式
8、定义交换律：交换律：r+s=s+r。幂等律：幂等律：r+r=r。加法运算零元素：加法运算零元素：r+=r。乘法运算单位元：乘法运算单位元：r=r=r。乘法运算零元素：乘法运算零元素：r=r=。L()=。L()=。L(a)=a。142.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。152.RE的形式定义的形式定义L(rn)=(L(r)n。rnrm=rn+m。一般地，一般地，r+r，
9、(rs)nrnsn，rssr。定义定义4-3：幂：幂r是字母表是字母表上的上的RERE，r的的n次次幂幂定义为定义为r0=。rn=rn-1r。162.RE的形式定义的形式定义例例4-2设设=0，100表示语言表示语言00；(0+1)*00(0+1)*表表示示所所有有的的至至少少含含两两个个连连续续0的的0、1串组成的语言；串组成的语言；(0+1)*1(0+1)9表表示示所所有有的的倒倒数数第第10个个字字符符为为1的串组成的语言；的串组成的语言；172.RE的形式定义的形式定义L(0+1)*011)=x|x是以是以011结尾的结尾的0、1串串；L(0+1+2+)=0n1m2k|m，n，k1；L
10、(0*1*2*)=0n1m2k|m，n，k0；L(1(0+1)*1+0(0+1)*0)=x|x的的开开头头字字符符与与尾尾字字符相同符相同。183.RE与与FA等价等价定义定义4-4：正则表达式：正则表达式r称为与称为与FA M等价，如果等价，如果L(r)=L(M)。从开始状态出发，根据状态之间按照转移所确定的从开始状态出发，根据状态之间按照转移所确定的后继关系，依次计算出所给后继关系，依次计算出所给FA的各个状态的各个状态q对应的对应的set(q)，并且最终得到相应的，并且最终得到相应的FA接受的语言的接受的语言的RE表表示。示。 寻找一种比较寻找一种比较“机械机械”的方法，使得计算机系统能
11、的方法，使得计算机系统能够自动完成够自动完成FA与与RE之间的转换。之间的转换。 193.1RE到到FA的等价变换的等价变换0对应的对应的FA01对应的对应的FA203.1RE到到FA的等价变换的等价变换0+1对应的对应的FA213.1RE到到FA的等价变换的等价变换0*对应的对应的FA223.1RE到到FA的等价变换的等价变换定理定理4-1 RERE表示的语言是表示的语言是RLRL。证明思路：证明思路：施归纳于正则表达式中所含的运算符的个数施归纳于正则表达式中所含的运算符的个数n，证，证明对于字母表明对于字母表上的任意正则表达式上的任意正则表达式r，存在，存在FA M，使得，使得L(M) =
12、 L(r) 。M恰有一个终止状态。恰有一个终止状态。M在终止状态下不作任何移动。在终止状态下不作任何移动。构造正则表达式对应的构造正则表达式对应的FA证明构造的证明构造的FA与与RE等价等价此处仅给出各种情况下此处仅给出各种情况下FA的构造方法。的构造方法。233.1RE到到FA的等价变换的等价变换r=r= r=a243.1RE到到FA的等价变换的等价变换对于已有正则表达式对于已有正则表达式r1与与r2对应的对应的FA：M1=(Q1，1，q01，f1)M2=(Q2，2，q02，f2)L(M1)=L(r1)，L(M2)=L(r2) 。Q1Q2=。由于正则表达式的运算包括加、乘和幂集，所以由于正则
13、表达式的运算包括加、乘和幂集，所以分分别别给给出出r=r1+r2；r=r1r2；r=r1*情情况况下下FA的的机机械械化化构构造造方方法法253.1RE到到FA的等价变换的等价变换第一种情况：第一种情况：r=r1+r2取取q0，f Q1Q2，令，令M=(Q1Q2q0，f，q0，f) (q0，)=q01，q02； 对对 qQ1，a，(q，a)=1(q，a); 对对 qQ2，a，(q，a)=2(q，a)； (f1，)=f； (f2，)=f。 263.1RE到到FA的等价变换的等价变换273.1RE到到FA的等价变换的等价变换M=(Q1Q2，q01，f2)对对 qQ1-f1，a(q，a)=1(q，a
14、)；对对 qQ2-f2，a(q，a)=2(q，a)； (f1，)=q0228第二种情况：第二种情况：r=r1r23.1RE到到FA的等价变换的等价变换293.1RE到到FA的等价变换的等价变换M=(Q1q0，f，q0，f)其中其中q0，f Q1，定义，定义为为对对 qQ1-f1，a,(q，a)=1(q，a)。 (f1，)=q01，f。 (q0，)=q01，f。30第三种情况：第三种情况：r=r1*3.1RE到到FA的等价变换的等价变换313.1RE到到FA的等价变换的等价变换按照以上方法构造一个给定按照以上方法构造一个给定RERE的等价的等价FA时，该时，该FA有可能含有许多的空移动。有可能含
15、有许多的空移动。可以按照自己对给定可以按照自己对给定RERE的的“理解理解”以及对以及对FA的的 “理解理解” “直接地直接地”构造出一个比较构造出一个比较“简单简单”的的FA。定理证明中所给的方法是机械的。由于定理证明中所给的方法是机械的。由于“直接地直接地”构造出的构造出的FA的正确性依赖于构造者的的正确性依赖于构造者的“理解理解”，所以它的正确性缺乏有力的保证。，所以它的正确性缺乏有力的保证。323.1RE到到FA的等价变换的等价变换例例4-3 构造与构造与 (0+1)*0+(00)*等价的等价的FA。解答：解答：设设r1=(0+1)*0 M1 r2=(00)* M2 r= r1+ r2
16、 M333.1RE到到FA的等价变换的等价变换r2=(00)*设设r3=00,则则r2=（r3）*343.1RE到到FA的等价变换的等价变换r3=00；设设r4=0则则r3=r4r4r3对应的对应的FA M3为：为：353.1RE到到FA的等价变换的等价变换到目前为止，得到的自动机如下图所示：363.1RE到到FA的等价变换的等价变换r1=(0+1)*0设设r5=1则则r1=（r4+r5）*r4373.1RE到到FA的等价变换的等价变换最终转换完成的FA如下图所示：383.2RL可以用可以用RE表示表示探讨如何从给定的探讨如何从给定的DFADFA构造等价的正则表达式。构造等价的正则表达式。计算
17、计算DFA的每个状态对应的集合的每个状态对应的集合字母表的克林字母表的克林闭包的等价分类，是具有启发意义的。闭包的等价分类，是具有启发意义的。这个计算过程难以这个计算过程难以“机械机械”地进行。地进行。计算计算qi到到qj的一类串的集合：的一类串的集合：Rkij。图上作业法。图上作业法。393.2RL可以用可以用RE表示表示定理定理4-2 RL可以用可以用RE表示。表示。构造与构造与FA等价的等价的RE403.2RL可以用可以用RE表示表示图上作业法操作步骤图上作业法操作步骤 预处理：预处理： 用标记为用标记为X和和Y的状态将的状态将M“括起来括起来”： 在在状状态态转转移移图图中中增增加加标
18、标记记为为X和和Y的的状状态态，从从标标记记为为X的的状状态态到到标标记记为为q0的的状状态态引引一一条条标标记记为为的的弧弧；从从标标记记为为q(qF)的的状状态态到到标标记记为为Y的的状状态态分分别别引引一一条标记为条标记为的弧。的弧。 去掉所有的不可达状态。去掉所有的不可达状态。413.2RL可以用可以用RE表示表示 对通过步骤对通过步骤(1)处理所得到的状态转移图重复如下处理所得到的状态转移图重复如下操作，直到该图中不再包含除了标记为操作，直到该图中不再包含除了标记为X和和Y外的其外的其他状态，并且这两个状态之间最多只有一条弧。他状态，并且这两个状态之间最多只有一条弧。并弧并弧将从将从
19、q到到p的标记为的标记为r1，r2，rg并行弧用从并行弧用从q到到p的、标记为的、标记为r1+r2+rg的弧取代这的弧取代这g个并行弧。个并行弧。423.2RL可以用可以用RE表示表示去状态去状态1 1如果从如果从q q到到p p有一条标记为有一条标记为r r1 1的弧，从的弧，从p p到到t t有一条标记有一条标记为为r r2 2的弧，不存在从状态的弧，不存在从状态p p到状态到状态p p的弧，将状态的弧，将状态p p和和与之关联的这两条弧去掉，用一条从与之关联的这两条弧去掉，用一条从q q到到t t的标记为的标记为r r1 1r r2 2的弧代替。的弧代替。 433.2RL可以用可以用RE
20、表示表示去状态去状态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的弧代替。的弧代替。 443.2RL可以用可以用RE表示表示去状态去状态3 3如果图中只有三个状态，而且不存在从标记为如果图中只有三个状态，而且不存在从标记为X的状的状态到达标记为态到达标记为Y的状
21、态的路，则将除标记为的状态的路，则将除标记为X的状态的状态和标记为和标记为Y的状态之外的第的状态之外的第3个状态及其相关的弧全个状态及其相关的弧全部删除。部删除。453.2RL可以用可以用RE表示表示 从标记为从标记为X的状态到标记为的状态到标记为Y的状态的弧的标记为的状态的弧的标记为所求的正则表达式。如果此弧不存在，则所求的正则所求的正则表达式。如果此弧不存在，则所求的正则表达式为表达式为。463.2RL可以用可以用RE表示表示例例4-4 求图求图4-14所示的所示的DFA等价的等价的RE。473.2RL可以用可以用RE表示表示预处理。预处理。483.2RL可以用可以用RE表示表示去掉状态去
22、掉状态q3。493.2RL可以用可以用RE表示表示去掉状态去掉状态q4。503.2RL可以用可以用RE表示表示合并从标记为合并从标记为q2的状态到标记为的状态到标记为Y的状态的两条并行的状态的两条并行弧。弧。513.2RL可以用可以用RE表示表示去掉状态去掉状态q0。523.2RL可以用可以用RE表示表示并弧。并弧。533.2RL可以用可以用RE表示表示去掉状态去掉状态q1。543.2RL可以用可以用RE表示表示去掉状态去掉状态q2。1*0(11*0)*0(00*111*0+00*10+11*0)(11*0)*0)*(00*+00*1)就是所求。就是所求。553.2RL可以用可以用RE表示表示
23、几点值得注意几点值得注意的问题的问题 如果去状态的顺序不一样，则得到的如果去状态的顺序不一样，则得到的RERE可能在形式可能在形式是不一样，但它们都是等价的。是不一样，但它们都是等价的。 当当DFADFA的终止状态都是不可达的时候，状态转移图的终止状态都是不可达的时候，状态转移图中必不存在从开始状态到终止状态的路。中必不存在从开始状态到终止状态的路。此此时，相，相应的的RERE为。 不计算自身到自身的弧，如果状态不计算自身到自身的弧，如果状态q q的入度为的入度为n n，出，出度为度为m m，则将状态，则将状态q q及其相关的弧去掉之后，需要添加及其相关的弧去掉之后，需要添加n*mn*m条新弧
24、。条新弧。563.2RL可以用可以用RE表示表示 对操作的步数施归纳，可以证明它的正确性。对操作的步数施归纳，可以证明它的正确性。推论推论4-1正则表达式与正则表达式与FA、正则文法等价，是正则语言、正则文法等价，是正则语言的表示模型。的表示模型。574.正则语言等价模型的总结正则语言等价模型的总结 AaB B(A，a)Aa qf(A，a)(q，a)=p qap(q， a)=pF qaRGDFANFARE-NFADFA(P,a)=NFA(P,a)NFA(q，a)=(q，a)图图上上作作业业法法归纳归纳585.小结小结 本章讨论了本章讨论了RLRL及其与及其与FA的等价性。的等价性。 字母表字母
25、表上的上的RERE用来表示用来表示上的上的RLRL。、a a（aa），是），是上的最基本的上的最基本的RERE，它们分别表示，它们分别表示语言语言、aa，以此为基础，如果，以此为基础，如果r r和和s s分别是分别是上的表示语言上的表示语言R R和和S S的的RERE，则，则r+sr+s、rs rs 、r*r*分别是分别是上的表示语言上的表示语言RSRS、RSRS、 R*R*的的RERE。如果。如果L(r)=L(s)L(r)=L(s)，则称，则称r r与与s s等价。等价。 595.小结小结 RERE对对乘乘、加加满满足足结结合合律律；乘乘对对加加满满足足左左、右右分分配配律律；加加满满足足交交换换率率和和幂幂等等率率；是是加加运运算算的的零零元元素；素；是乘运算的单位元；是乘运算的单位元；是乘运算的零元素。是乘运算的零元素。 RERE是是RLRL的一种描述。容易根据的一种描述。容易根据RERE构造出与它等构造出与它等价的价的FA。反过来，可以用图上作业法构造出与给。反过来，可以用图上作业法构造出与给定的定的DFA等价的等价的RERE。 RLRL的的5 5种等价描述模型转换图。种等价描述模型转换图。 60课后作业课后作业课后习题-1-（8）、（9）课后习题-5（1）课后习题-6（2）图4-2561
