形式语言-第4章-正则表达式-课件.ppt

1、2022-10-291第第4章章 正则表达式正则表达式 正则文法擅长语言的产生，有穷状态自动正则文法擅长语言的产生，有穷状态自动机擅长语言的识别。机擅长语言的识别。本章讨论正则语言的正则表达式描述。它本章讨论正则语言的正则表达式描述。它在对正则语言的表达上具有特殊的优势，在对正则语言的表达上具有特殊的优势，为正则语言的计算机处理提供了方便条件。为正则语言的计算机处理提供了方便条件。简洁、更接近语言的集合表示和语言的计算机简洁、更接近语言的集合表示和语言的计算机表示等。表示等。2022-10-292第第4章章 正则表达式正则表达式 主要内容主要内容 典型典型RE的构造。的构造。与与RE等价等价F

2、A的构造方法。的构造方法。与与DFA等价的等价的RE的构造。的构造。重点重点 RE的概念。的概念。RE与与DFA的等价性。的等价性。难点：难点：RE与与DFA的等价性证明。的等价性证明。2022-10-2934.启示启示 产生语言产生语言anbmck|n，m，k1aicnbxam|i0,n1,m2,x为为d和和e组成的串组成的串 的正则文法为的正则文法为AaA|aB|cEBbB|bCCcC|cE cE|bFFdF|eF|aHHaH|a2022-10-2944.启示启示 接受此语言的接受此语言的NFA M 2022-10-2954.启示启示 计算集合计算集合 set(q)set(A)=an|n0

3、=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+2022-10-2964.启示启示 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+aL(M)=set(D)set(H)=a+b+c+a*c+bd，e*a+a2022-10-2974.

4、启示启示 根据集合运算的定义，根据集合运算的定义，d，e=de。从而，从而，d，e*=(de)*。这样可以将这样可以将L(M)写成如下形式：写成如下形式：L(M)=a+b+c+a*c+b(de)*a+a 记作：记作：a+b+c+a*c+b(d+e)*a+a=aa*bb*cc*+a*cc*b(d+e)*aaa*2022-10-2984.2 RE的形式定义的形式定义 正则表达式正则表达式(regular expression(regular expression，RE)RE)是是上的上的RERE，它表示语言，它表示语言；是是上的上的RERE，它表示语言，它表示语言；对于对于 aa，a a是是上的上

5、的RERE，它表示，它表示语言语言aa；2022-10-2994.2 RE的形式定义的形式定义 如果如果r r和和s s分别是分别是上表示语言上表示语言R R和和S S的的RERE，则：则：r r与与s s的的“和和”(r+s)(r+s)是是上的上的RERE，(r+s)(r+s)表表达的语言为达的语言为RSRS；r r与与s s的的“乘积乘积”(rs)(rs)是是上的上的RERE，(rs)(rs)表表达的语言为达的语言为RSRS；r r的克林闭包的克林闭包(r(r*)是是上的上的RERE，(r(r*)表达的语表达的语言为言为R R*。只有满足、的才是只有满足、的才是上的上的RERE。2022-

6、10-29104.2 RE的形式定义的形式定义 例例 4-1 4-1 设设=0=0，11 0 0，表示语言，表示语言00；1 1，表示语言，表示语言11；(0+1)(0+1)，表示语言，表示语言00，11；(01)(01)，表示语言，表示语言0101；(0+1)(0+1)*)，表示语言，表示语言00，11*；(00)(00)(00)(00)*)，表示语言，表示语言00000000*；2022-10-29114.2 RE的形式定义的形式定义 (0+1)(0+1)*)(0+1)(0+1)(0+1)(0+1)*),),表示语言表示语言00，11+；(0+1)(0+1)*)000)(0+1)000)(

7、0+1)*)，表示，表示00，11上的至少含有上的至少含有3 3个连续个连续0 0的串组成的语言；的串组成的语言；(0+1)(0+1)*)0)1)0)1)，表示所有以，表示所有以0101结尾的结尾的0 0、1 1字符串组成的语言；字符串组成的语言；(1(0+1)(1(0+1)*)0)0)，表示所有以，表示所有以1 1开头，并开头，并且以且以0 0结尾的结尾的0 0、1 1字符串组成的语言。字符串组成的语言。2022-10-29124.2 RE的形式定义的形式定义 约定约定 r r的正闭包的正闭包r r+表示表示r r与与(r(r*)的乘积以及的乘积以及(r(r*)与与r r的乘积：的乘积：r

8、r+=(r(r=(r(r*)=(r)=(r*)r)r)闭包运算的优先级最高，乘运算的优先级闭包运算的优先级最高，乘运算的优先级次之，加运算次之，加运算“+”+”的优先级最低。所以，的优先级最低。所以，在意义明确时，可以省略其中某些括号。在意义明确时，可以省略其中某些括号。(0+1)(0+1)*)000)(0+1)000)(0+1)*)=(0+1)=(0+1)*000(0+1)000(0+1)*2022-10-29134.2 RE的形式定义的形式定义(0+1)(0+1)*)(0+1)(0+1)(0+1)(0+1)*)=(0+1)=(0+1)*(0+(0+1)(0+1)1)(0+1)*在意义明确时

9、，在意义明确时，RE rRE r表示的语言记为表示的语言记为L(r)L(r)，也可以直接地记为，也可以直接地记为r r。加、乘、闭包运算均执行左结合规则。加、乘、闭包运算均执行左结合规则。2022-10-29144.2 RE的形式定义的形式定义 相等相等(equivalence)(equivalence)r r、s s是字母表是字母表上的一个上的一个RERE，如果，如果L(r)=L(s)L(r)=L(s)，则称，则称r r与与s s相等，记作相等，记作r=s r=s。相等也称为等价。相等也称为等价。几个基本结论几个基本结论 结合律：结合律：(rs)t=r(st)(rs)t=r(st)(r+s)

10、+t=r+(s+t)(r+s)+t=r+(s+t)分配律：分配律：r(s+t)=rs+rtr(s+t)=rs+rt (s+t)r=sr+tr (s+t)r=sr+tr2022-10-29154.2 RE的形式定义的形式定义 交换律：交换律：r+s=s+rr+s=s+r。幂等律：幂等律：r+r=rr+r=r。加法运算零元素：加法运算零元素：r+r+=r=r。乘法运算单位元：乘法运算单位元：r=r=rr=r=r。乘法运算零元素：乘法运算零元素：r r=r=r=。L(L()=)=。L()=L()=。L(a)=aL(a)=a。2022-10-29164.2 RE的形式定义的形式定义 L(rs)=L(r

11、)L(s)L(rs)=L(r)L(s)。L(r+s)=L(r)L(s)L(r+s)=L(r)L(s)。L(rL(r*)=(L(r)=(L(r)*。L(L(*)=)=。L(r+)L(r+)*)=L(r)=L(r*)。L(rL(r*)*)=L(r)=L(r*)。L(rL(r*s s*)*)=L(r+s)=L(r+s)*)。如果如果L(r)L(r)L(s)L(s)，则，则r+s=sr+s=s。2022-10-29174.2 RE的形式定义的形式定义 L(r L(rn n)=(L(r)=(L(r)n n。r rn nr rm m=r=rn+m n+m。一般地，一般地，r+rr+r，(rs)(rs)n

12、n r rn ns sn n，rssrrssr。幂幂 r r是字母表是字母表上的上的RERE，r r的的n n次幂定义为次幂定义为 r r0 0=。r rn n=r=rn-1n-1r r。2022-10-29184.2 RE的形式定义的形式定义 例例 4-2 4-2 设设=0=0，110000表示语言表示语言0000；(0+1)(0+1)*00(0+1)00(0+1)*表示所有的至少含两表示所有的至少含两个连续个连续0 0的的0 0、1 1串组成的语言；串组成的语言；(0+1)(0+1)*1(0+1)1(0+1)9 9表示所有的倒数第表示所有的倒数第1010个个字符为字符为1 1的串组成的语言

13、；的串组成的语言；2022-10-29194.2 RE的形式定义的形式定义L(0+1)L(0+1)*011)=x|x011)=x|x是以是以011011结尾的结尾的0 0、1 1串串；L(0L(0+1 1+2 2+)=0)=0n n1 1m m2 2k k|m|m，n n，k1k1；L(0L(0*1 1*2 2*)=0)=0n n1 1m m2 2k k|m|m，n n，k0k0；L(1(0+1)L(1(0+1)*1+0(0+1)1+0(0+1)*0)=x|x0)=x|x的开头字符的开头字符与尾字符相同与尾字符相同。2022-10-29204.3 RE与与FA等价等价 正则表达式正则表达式r

14、r称为与称为与FA MFA M等价，如果等价，如果L(r)=L(M)L(r)=L(M)。从开始状态出发，根据状态之间按照转移从开始状态出发，根据状态之间按照转移所确定的后继关系，依次计算出所给所确定的后继关系，依次计算出所给FAFA的的各个状态各个状态q q对应的对应的set(q)set(q)，并且最终得到相，并且最终得到相应的应的FAFA接受的语言的接受的语言的RERE表示。表示。寻找一种比较寻找一种比较“机械机械”的方法，使得计算的方法，使得计算机系统能够自动完成机系统能够自动完成FAFA与与RERE之间的转换。之间的转换。2022-10-29214.3.1 RE到到FA的等价变换的等价变

15、换 0 0对应的对应的FAFA 0101对应的对应的FAFA2022-10-29224.3.1 RE到到FA的等价变换的等价变换 0+1对应的对应的FA2022-10-29234.3.1 RE到到FA的等价变换的等价变换 0*对应的对应的FA2022-10-29244.3.1 RE到到FA的等价变换的等价变换 定理定理 4-1 RE4-1 RE表示的语言是表示的语言是RLRL。证明：证明：施归纳于正则表达式中所含的运算符施归纳于正则表达式中所含的运算符的个数的个数n n，证明对于字母表，证明对于字母表上的任意上的任意正则表达式正则表达式r r，存在，存在FA MFA M，使得，使得L(M)=L

16、(M)=L(r)L(r)。M M恰有一个终止状态。恰有一个终止状态。M M在终止状态下不作任何移动。在终止状态下不作任何移动。2022-10-29254.3.1 RE到到FA的等价变换的等价变换 n=0 r=r=r=a 2022-10-29264.3.1 RE到到FA的等价变换的等价变换 设结论对于设结论对于n=k时成立，此时有如下时成立，此时有如下FA：M1=(Q1，1，q01，f1)M2=(Q2，2，q02，f2)L(M1)=L(r1)，L(M2)=L(r2)。Q1Q2=。n=k2022-10-2927n=k+1 r=r1+r2取取q q0 0，f f Q Q1 1QQ2 2，令，令M=(

17、QM=(Q1 1QQ2 2qq0 0，ff，q q0 0，f)f)(q(q0 0，)=q)=q0101，q q0202；对对 qQqQ1 1，aa，(q(q，a)=a)=1 1(q(q，a);a);对对 qQqQ2 2，aa，(q(q，a)=a)=2 2(q(q，a)a)；(f(f1 1，)=f)=f；(f(f2 2，)=f)=f。2022-10-29284.3.1 RE到到FA的等价变换的等价变换 n=k+1 r=r1+r2 2022-10-29294.3.1 RE到到FA的等价变换的等价变换 M=(Q1Q2，q01，f2)对对 qQ1-f1，a(q，a)=1(q，a)；对对 qQ2-f2，

18、a(q，a)=2(q，a)；(f1，)=q022022-10-29304.3.1 RE到到FA的等价变换的等价变换 r=r1r2 2022-10-29314.3.1 RE到到FA的等价变换的等价变换 M=(Q1q0，f，q0，f)其中其中q0，f Q1，定义，定义为为 对对 q Q1-f1，a ，(q，a)=1(q，a)。(f1，)=q01，f。(q0，)=q01，f。2022-10-29324.3.1 RE到到FA的等价变换的等价变换 r=r1*2022-10-29334.3.1 RE到到FA的等价变换的等价变换 按照定理按照定理4-1证明给出的方法构造一个给定证明给出的方法构造一个给定RE

19、RE的等价的等价FA时，该时，该FA有可能含有许多的空有可能含有许多的空移动。移动。可以按照自己对给定可以按照自己对给定RERE的的“理解理解”以及对以及对FA的的 “理解理解”“直接地直接地”构造出一个比构造出一个比较较“简单简单”的的FA。定理证明中所给的方法是机械的。由于定理证明中所给的方法是机械的。由于“直接地直接地”构造出的构造出的FA的正确性依赖于构的正确性依赖于构造者的造者的“理解理解”，所以它的正确性缺乏有，所以它的正确性缺乏有力的保证。力的保证。2022-10-29344.3.1 RE到到FA的等价变换的等价变换 例例 4-3 构造与构造与 (0+1)*0+(00)*等价的等

20、价的FA。2022-10-29354.3.1 RE到到FA的等价变换的等价变换 按照对按照对(0+1)*0+(00)*的的“理解理解”“直接地直接地”构造出的构造出的FA。2022-10-29364.3.2 RL可以用可以用RE表示表示 计算计算DFA的每个状态对应的集合的每个状态对应的集合字母字母表的克林闭包的等价分类，是具有启发意表的克林闭包的等价分类，是具有启发意义的。义的。这个计算过程难以这个计算过程难以“机械机械”地进行。地进行。计算计算q1到到q2的一类串的集合：的一类串的集合：Rkij。图上作业法。图上作业法。2022-10-29374.3.2 RL可以用可以用RE表示表示定理定

21、理4-2 RL可以用可以用RE表示。表示。设设DFA M=(q1，q2，qn，q1，F)Rkij=x|(qi，x)=qj而且对于而且对于x的任意前缀的任意前缀y(yx，y)，如果，如果(qi，y)=ql，则，则lk。2022-10-29384.3.2 RL可以用可以用RE表示表示R0ij=a|(qi，a)=qj如果如果ij a|(qi，a)=qj如果如果i=j Rkij=Rk-1ik(Rk-1kk)*Rk-1kj Rk-1ij FqnffRML1)(2022-10-29394.3.2 RL可以用可以用RE表示表示 图上作业法图上作业法 启示启示2022-10-29404.3.2 RL可以用可以

22、用RE表示表示 图上作业法操作步骤图上作业法操作步骤 预处理：预处理：用标记为用标记为X和和Y的状态将的状态将M“括起来括起来”：在状态转移图中增加标记为在状态转移图中增加标记为X和和Y的状态，的状态，从标记为从标记为X的状态到标记为的状态到标记为q0的状态引一条的状态引一条标记为标记为的弧；从标记为的弧；从标记为q(qF)的状态到的状态到标记为标记为Y的状态分别引一条标记为的状态分别引一条标记为的弧。的弧。去掉所有的不可达状态。去掉所有的不可达状态。2022-10-29414.3.2 RL可以用可以用RE表示表示 对通过步骤对通过步骤(1)处理所得到的状态转移图重处理所得到的状态转移图重复如

23、下操作，直到该图中不再包含除了标记复如下操作，直到该图中不再包含除了标记为为X和和Y外的其他状态，并且这两个状态之间外的其他状态，并且这两个状态之间最多只有一条弧。最多只有一条弧。并弧并弧 将从将从q到到p的标记为的标记为r1，r2，rg并行弧用从并行弧用从q到到p的、标记为的、标记为r1+r2+rg的弧取代这的弧取代这g个并行个并行弧。弧。2022-10-29424.3.2 RL可以用可以用RE表示表示 去状态去状态1 1 如果从如果从q q到到p p有一条标记为有一条标记为r r1 1的弧，从的弧，从p p到到t t有一有一条标记为条标记为r r2 2的弧，不存在从状态的弧，不存在从状态p

24、 p到状态到状态p p的弧，的弧，将状态将状态p p和与之关联的这两条弧去掉，用一条和与之关联的这两条弧去掉，用一条从从q q到到t t的标记为的标记为r r1 1r r2 2的弧代替。的弧代替。去状态去状态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的弧代替。的

25、弧代替。2022-10-29434.3.2 RL可以用可以用RE表示表示 去状态去状态3 3 如果图中只有三个状态，而且不存在从标记为如果图中只有三个状态，而且不存在从标记为X的状态到达标记为的状态到达标记为Y的状态的路，则将除标的状态的路，则将除标记为记为X的状态和标记为的状态和标记为Y的状态之外的第的状态之外的第3个状个状态及其相关的弧全部删除。态及其相关的弧全部删除。2022-10-29444.3.2 RL可以用可以用RE表示表示 从标记为从标记为X的状态到标记为的状态到标记为Y的状态的弧的状态的弧的标记为所求的正则表达式。如果此弧不的标记为所求的正则表达式。如果此弧不存在，则所求的正则

26、表达式为存在，则所求的正则表达式为。2022-10-29454.3.2 RL可以用可以用RE表示表示 例例 4-4 求图求图4-14所示的所示的DFA等价的等价的RE。2022-10-29464.3.2 RL可以用可以用RE表示表示 预处理。预处理。2022-10-29474.3.2 RL可以用可以用RE表示表示 去掉状态去掉状态q3。2022-10-29484.3.2 RL可以用可以用RE表示表示 去掉状态去掉状态q4。2022-10-29494.3.2 RL可以用可以用RE表示表示 合并从标记为合并从标记为q2的状态到标记为的状态到标记为Y的状态的的状态的两条并行弧。两条并行弧。2022-

27、10-29504.3.2 RL可以用可以用RE表示表示 去掉状态去掉状态q0。2022-10-29514.3.2 RL可以用可以用RE表示表示 并弧。并弧。2022-10-29524.3.2 RL可以用可以用RE表示表示 去掉状态去掉状态q1。2022-10-29534.3.2 RL可以用可以用RE表示表示 去掉状态去掉状态q2。1*0(11*0)*0(00*111*0+00*10+11*0)(11*0)*0)(00*+00*1)就是所求。就是所求。2022-10-29544.3.2 RL可以用可以用RE表示表示 几点值得注意几点值得注意的问题的问题 如果去状态的顺序不一样，则得到的如果去状态

28、的顺序不一样，则得到的RERE可能可能在形式是不一样，但它们都是等价的。在形式是不一样，但它们都是等价的。当当DFADFA的终止状态都是不可达的时候，状态转的终止状态都是不可达的时候，状态转移图中必不存在从开始状态到终止状态的路。移图中必不存在从开始状态到终止状态的路。此时，相应的此时，相应的RERE为为。不计算自身到自身的弧，如果状态不计算自身到自身的弧，如果状态q q的入度为的入度为n n，出度为，出度为m m，则将状态，则将状态q q及其相关的弧去掉之及其相关的弧去掉之后，需要添加后，需要添加n n*m m条新弧。条新弧。2022-10-29554.3.2 RL可以用可以用RE表示表示

29、对操作的步数施归纳，可以证明它的正确性。对操作的步数施归纳，可以证明它的正确性。推论推论4-1 正则表达式与正则表达式与FA、正则文法等、正则文法等价，是正则语言的表示模型。价，是正则语言的表示模型。2022-10-29564.4 正则语言等价模型的总结正则语言等价模型的总结 AaB B(A,a)Aa qf(A,a)(q,a)=p qap(q,a)=pF qaRGGDFANFARE-NFADFA(P,a)=NFA(P,a)NFA(q，a)=(q，a)图上作业图上作业法法归纳归纳2022-10-29574.5 小结小结 本章讨论了本章讨论了RLRL及其与及其与FA的等价性。的等价性。字母表字母表

30、上的上的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等等价。价。2022-10-29584.5 小结小结 RERE对乘、加满足结合律；乘对加满足左、对乘、加满足结合律；乘对加满足左、右分配律；加满

31、足交换率和幂等率；右分配律；加满足交换率和幂等率；是是加运算的零元素；加运算的零元素；是乘运算的单位元；是乘运算的单位元；是乘运算的零元素。是乘运算的零元素。RERE是是RLRL的一种描述。容易根据的一种描述。容易根据RERE构造出构造出与它等价的与它等价的FA。反过来，可以用图上作业。反过来，可以用图上作业法构造出与给定的法构造出与给定的DFA等价的等价的RERE。RLRL的的5 5种等价描述模型转换图。种等价描述模型转换图。2022-10-2959习题 写出下列语言的正则表达式写出下列语言的正则表达式 00，11*00，11+x|x x00，11+且且x x的第十个字符是的第十个字符是1

32、1 x|x x00，11+且且x x以以0 0开头以开头以1 1结尾结尾 x|x x00，11+且且x x中至少含两个中至少含两个1 1 x|x x00，11*和和x x如果以如果以1 1结尾，则它的长度结尾，则它的长度为偶数；如果为偶数；如果x x以以0 0结尾，则它的长度为奇数结尾，则它的长度为奇数 x|x x00，11*且且x x中不含形如中不含形如0000的子串的子串 2022-10-2960习题 理解如下正则表达式，说明它们表示的语言理解如下正则表达式，说明它们表示的语言 （00+1100+11）+(0+01+001)(0+01+001)*(+0+00)(+0+00)(0+1)(0+1)(0+1)(0+1)*+(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)*(0+1)(0+1)(0+1)(0+1)*(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)*构造下列正则表达式的等价构造下列正则表达式的等价FAFA(0+1)(0+1)(0+1)(0+1)*+(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)*2022-10-2961习题 构造等价如图所示构造等价如图所示DFADFA的正则表达式的正则表达式q0q1q2q3S111000，100