04 正则表达式.ppt

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

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

2、造。34.1启示启示产产生生语语言言anbmck|n,m,k1aicnbxam|i0,n1,m2,x为为d 和和e组组成成的的串串的正则文法为的正则文法为AaA|aB|cEBbB|bCCcC|cEcE|bFFdF|eF|aHHaH|a44.1启示启示计算集合计算集合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+54.1启示启示set(E)=set(A)cc*=a*cc*=a*c+set(F)=se

3、t(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)set(H)=a+b+c+a*c+d,e*a+a64.1启示启示根据集合运算的定义，根据集合运算的定义，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*74.2正则表达式的形式定义正则表达式的形式定义q正

4、则表达式正则表达式(regularexpression，RE)设设是一个字母表，是一个字母表，(1)是是上的正则表达式，它表示语言上的正则表达式，它表示语言；(2)是是上的正则表达式，它表示语言上的正则表达式，它表示语言；(3)对于对于 a，a 是是上的正则表达式，它表示语言上的正则表达式，它表示语言a；(4)如果如果r 和和s 分别是分别是 上表示语言上表示语言R和和S的的RE，则：，则：r 与与s 的的“和和”(r+s)是是上的上的RE，(r+s)表达的语言为表达的语言为RS；r 与与s 的的“乘积乘积”(rs)是是上的上的RE，(rs)表达的语言为表达的语言为RS；r 的的克林闭包克林闭

5、包(r*)是是上的上的RE，(r*)表达的语言为表达的语言为R*。(5)只有满足只有满足(1),(2),(3),(4)的表达式才是的表达式才是上的正则表达式。上的正则表达式。8正则表达式举例正则表达式举例 设设=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)*)，表表示示

6、0,1上上的的至至少少含含有有3个个连连续续0的的串串组组成成的的语语言；言；(9)(0+1)*)0)1)，表示所有以，表示所有以01结尾的结尾的0,1字符串组成的语言；字符串组成的语言；(10)(1(0+1)*)0)，表表示示所所有有以以1开开头头，并并且且以以0结结尾尾的的0,1字字符符串串组组成成的的语言。语言。9约定(1)r的正闭包的正闭包r+表示表示r 与与(r*)的乘积以及的乘积以及(r*)与与r的乘积：的乘积：r+=(r(r*)=(r*)r)(2)闭包运算的优先级最高，乘运算的优先级次之，加运算闭包运算的优先级最高，乘运算的优先级次之，加运算“+”的优先的优先级最低。所以，在意义

7、明确时，可以省略其中某些括号。级最低。所以，在意义明确时，可以省略其中某些括号。(0+1)*)000)(0+1)*)=(0+1)*000(0+1)*(0+1)*)(0+1)(0+1)*)=(0+1)*(0+1)(0+1)*(3)在意义明确时，在意义明确时，REr 表示的语言记为表示的语言记为L(r)，也可以直接地记为，也可以直接地记为r。(4)加、乘、闭包运算均执行左结合规则。加、乘、闭包运算均执行左结合规则。(5)相等相等(equivalence)r,s是字母表是字母表上的一个上的一个RE，如果，如果L(r)=L(s)，则称，则称r 与与s相等，记作相等，记作r=s。相等也称为等价。相等也称

8、为等价。10基本结论(1)结合律：结合律：(rs)t=r(st)(r+s)+t=r+(s+t)(2)分配律：分配律：r(s+t)=rs+rt(s+t)r=sr+tr(3)交换律：交换律：r+s=s+r(4)幂等律：幂等律：r+r=r(5)加法运算单位元：加法运算单位元：r+=r(6)乘法运算单位元：乘法运算单位元：r=r=r(7)乘法运算零元素：乘法运算零元素：r=r=(8)L()=(9)L()=。(10)L(a)=a。11基本结论(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*

9、)。(16)L(r*)*)=L(r*)。(17)L(r*s*)*)=L(r+s)*)。(18)如果如果L(r)L(s)，则，则r+s=s。12幂的定义q幂幂r是字母表是字母表上的上的RE，r的的n次幂定义为次幂定义为(1)r0=。(2)rn=rn-1r。q基本结论基本结论(19)L(rn)=(L(r)n。(20)rnrm=rn+m。一般地，一般地，r+r，(rs)nrnsn，rssr。13正则表达式举例设设=0,1q00表示语言表示语言00；q(0+1)*00(0+1)*表示所有的至少含两个连续表示所有的至少含两个连续0的的0,1串组成的语言；串组成的语言；qL(0+1)*011)=x|x 是

10、以是以011结尾的结尾的0,1串串；qL(0+1+2+)=0n1m2k|m,n,k1；qL(0*1*2*)=0n1m2k|m,n,k0；qL(1(0+1)*1+0(0+1)*0)=x|x的开头字符与尾字符相同的开头字符与尾字符相同。14举例q构造一个正则表达式，使它能代表十进制正整数的集合。构造一个正则表达式，使它能代表十进制正整数的集合。(1+2+3+4+5+6+7+8+9)(0+1+2+3+4+5+6+7+8+9)*q构造一个正则表达式，使它能代表如下的集合构造一个正则表达式，使它能代表如下的集合S：S的每个元素都是倒的每个元素都是倒数第十个字符是数第十个字符是1的的0、1串。串。(0+1

11、)*1(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)*1(0+1)9构造一个正则表达式，使它能代表能被构造一个正则表达式，使它能代表能被3整除的二进制数？整除的二进制数？154.3 RE 与 FA 等价 q正则表达式正则表达式r称为与称为与FAM等价，如果等价，如果L(r)=L(M)。q从开始状态出发，根据状态之间按照转移所确定的后继关系，依次计从开始状态出发，根据状态之间按照转移所确定的后继关系，依次计算出所给算出所给FA的各个状态的各个状态q对应的对应的set(q)，并且最终得到相应的，并且最终得到相应的FA接接受的语言的受的语言的RE

12、表示。表示。q寻找一种比较寻找一种比较“机械机械”的方法，使得计算机系统能够自动完成的方法，使得计算机系统能够自动完成FA与与RE之间的转换。之间的转换。16RE到FA的等价变换 0对应的对应的FA01对应的对应的FA0+1对应的对应的FA0*对应的对应的FA17定理4-1 定理定理4-1正则表达式表示的语言是正则语言正则表达式表示的语言是正则语言。证明思路：证明思路：施归纳于正则表达式中所含的运算符的个数施归纳于正则表达式中所含的运算符的个数n，证明证明对于字母表对于字母表上的任意正则表达式上的任意正则表达式r，存在，存在FAM，使得使得L(M)=L(r)，并且，并且M恰有一个终止状态。恰有

13、一个终止状态。M在终止状态下不作任何移动。在终止状态下不作任何移动。18定理 4-1当当n=0时，有如下时，有如下3种情况：种情况：(1)r=(2)r=(3)r=a 19定理 4-1假设结论对于假设结论对于nk时成立，则当时成立，则当n=k+1时，时，r 有有3种情况：种情况：(1)r=r1+r2(2)r=r1r2(3)r=r1*此时此时r1,r2中所含的运算符的个数不会大于中所含的运算符的个数不会大于k。由归纳假设，存在满足要求的由归纳假设，存在满足要求的NFA：M1=(Q1,1,q01,f1)M2=(Q2,2,q02,f2)使得使得L(M1)=L(r1)，L(M2)=L(r2)。由于可以对

14、状态进行重新命名，不妨设由于可以对状态进行重新命名，不妨设Q1Q2=。20定理 4-1(1)r=r1+r2q01M1f1q02M2f2fq0S取取q0,f Q1Q2，令，令M=(Q1Q2q0,f,q0,f)(q0,)=q01,q02；对对 qQ1-f1，a,(q,a)=1(q,a);对对 qQ2-f2，a,(q,a)=2(q,a)；(f1,)=f；(f2,)=f。21定理 4-1在在M1和和M2中，对于中，对于 a，1(f1,a)=2(f2,a)=，所以所以M1和和M2中的所有状态转移均包含在中的所有状态转移均包含在M 的状态转移中的状态转移中。往证往证L(r1+r2)=L(M)。由归纳假设由

15、归纳假设L(r1)=L(M1)，L(r2)=L(M2)根据正则表达式的定义根据正则表达式的定义L(r1+r2)=L(r1)L(r2)只需证明只需证明L(M)=L(M1)L(M2)先证先证L(M1)L(M2)L(M)设设xL(M1)L(M2)，从而有，从而有xL(M1)或者或者xL(M2)。22定理 4-1当当xL(M1)时，时，1(q01,x)=f1(q0,x)=(q0,x)=(q0,),x)=(q01,q02,x)=(q01,x)(q02,x)=(q01,x),)(q02,x),)=(1(q01,x),)(2(q02,x),)=(f1,)(2(q02,x),)=f(2(q02,x),)即即x

16、L(M)同理可证，当同理可证，当xL(M2)时，时，xL(M)。故故L(M1)L(M2)L(M)。23定理 4-1再再证证L(M)L(M1)L(M2)。设设xL(M)，即有，即有f(q0,x)(q0,x)=(q0,x)=(q0,),x)=(q01,q02,x)=(q01,x)(q02,x)=(q01,x),)(q02,x),)=(1(q01,x),)(2(q02,x),)f(q0,x)，并且此，并且此时时M的最后一次移的最后一次移动动必是根据如下两个定必是根据如下两个定义义式之一式之一进进行的移行的移动动：(f1,)=f，(f2,)=f 24定理 4-1如果根据定如果根据定义义式式(f1,)=

17、f 进进行的最后一次移行的最后一次移动动，注意到注意到Q1Q2=，则此时必有，则此时必有(q01,x)=f1即即 xL(M1)。如果根据定如果根据定义义式式(f2,)=f 进进行的最后一次移行的最后一次移动动，注意到注意到Q1Q2=，则此时必有，则此时必有(q02,x)=f2即即 xL(M2)。综上，综上，xL(M1)L(M2)所以所以L(M)L(M1)L(M2)。综上所述，综上所述，L(M)=L(M1)L(M2)。这说明这说明M与与r 等价等价。25定理 4-1q01M1f1q02M2f2S(2)r=r1r2M=(Q1Q2,q01,f2)对对 qQ1-f1，a(q,a)=1(q,a)；对对

18、qQ2，a(q,a)=2(q,a)；(f1,)=q02仅仅需需证证明明L(M)=L(M1)L(M2)。26定理 4-1(3)r=r1*q01M1f1fSq0M=(Q1q0,f,q0,f)其中其中q0,f Q1，定，定义义为为对对 qQ1-f1，a,(q,a)=1(q,a)。(f1,)=q01,f。(q0,)=q01,f。27定理 4-1q按照定理按照定理4-1证明给出的方法构造一个给定证明给出的方法构造一个给定RE的等价的等价FA时，该时，该FA有可能含有许多的空移动。有可能含有许多的空移动。q可以按照自己对给定可以按照自己对给定RE的的“理解理解”以及对以及对FA的的“理解理解”“直接地直接

19、地”构造出一个比较构造出一个比较“简单简单”的的FA。q定理证明中所给的方法是机械的。由于定理证明中所给的方法是机械的。由于“直接地直接地”构造出的构造出的FA的正的正确性依赖于构造者的确性依赖于构造者的“理解理解”，所以它的正确性缺乏有力的保证。，所以它的正确性缺乏有力的保证。28定理 4-1的举例构造与构造与 (0+1)*0+(00)*等价的等价的FA。(1)构造与构造与0等价的等价的-NFAM1。0(2)构造构造11(3)构造构造0+1(4)构造构造(0+1)*(5)构造构造(0+1)*00(6)构造构造0000(7)构造构造(00)*(8)构造与构造与(0+1)*0+(00)*等价的等

20、价的FA。S29定理 4-1的举例q按照对按照对(0+1)*0+(00)*的的“理解理解”“直接地直接地”构造出的构造出的 FA。30正则语言可以用正则表达式表示 正则表达式表示的是正则语言。正则表达式表示的是正则语言。是否所有的正则语言都可以用正则表达式表示？是否所有的正则语言都可以用正则表达式表示？q由于由于DFA是正则语言的等价描述模型，可以探讨如何从给定的是正则语言的等价描述模型，可以探讨如何从给定的DFA构构造等价的正则表达式。造等价的正则表达式。计算等价类的方法计算等价类的方法。逐个地计算出。逐个地计算出DFA的状态对应的集合，然后用的状态对应的集合，然后用RE表示每个终止状态表示

21、的集合，最后将这些表示每个终止状态表示的集合，最后将这些RE加起来可以获加起来可以获得得DFA对应的对应的RE。计算计算Rkij 的方法的方法。构造出描述标记。构造出描述标记DFA转移图中特定路径的串的集转移图中特定路径的串的集合表达式。然后归纳地构造让路径经过越来越多的状态集合的表达合表达式。然后归纳地构造让路径经过越来越多的状态集合的表达式。式。图上作业法图上作业法。通过对。通过对DFA的状态转移图的处理来获取它相应的的状态转移图的处理来获取它相应的RE。q定理定理4-2正则语言可以用正则表达式表示。正则语言可以用正则表达式表示。31图上作业法q通过对通过对DFA的状态转移图的处理来获取它

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

23、作，直到该图中不直到该图中不再包含除了标记为再包含除了标记为X和和Y外的其他状态，并且这两个状态之间最多只外的其他状态，并且这两个状态之间最多只有一条弧有一条弧。q并弧并弧将从将从q 到到p的标记为的标记为r1,r2,rg并行弧用从并行弧用从q到到p的、标记为的、标记为r1+r2+rg的弧取代这的弧取代这g 个并行弧。个并行弧。33图上作业法q去状态去状态1如果从如果从q 到到p 有一条标记为有一条标记为r1的弧，从的弧，从p 到到t 有一条标记为有一条标记为r2的弧的弧，不，不存在从状态存在从状态p到状态到状态p的弧，将状态的弧，将状态p和与之关联的这两条弧去掉，用一和与之关联的这两条弧去掉

24、，用一条从条从q到到t的标记为的标记为r1r2的弧代替。的弧代替。q去状态去状态2如果从如果从q到到p有一条标记为有一条标记为r1的弧的弧，从从p到到t有一条标记为有一条标记为r2的弧的弧，从，从状态状态p到状态到状态p标记为标记为r3的弧的弧，将状态，将状态p和与之关联的这三条弧去掉，用一条从和与之关联的这三条弧去掉，用一条从q到到t的标记为的标记为r1r3*r2的弧代替。的弧代替。q去状态去状态3如果图中只有三个状态，而且不存在从标记为如果图中只有三个状态，而且不存在从标记为 X的状态到达标记为的状态到达标记为 Y的状态的路，则将除标记为的状态的路，则将除标记为 X的状态和标记为的状态和标

25、记为 Y的状态之外的第的状态之外的第3个个状态及其相关的弧全部删除。状态及其相关的弧全部删除。从标记为从标记为X的状态到标记为的状态到标记为Y的状态的弧的标记为所求的正则表达式。的状态的弧的标记为所求的正则表达式。如果此弧不存在，则所求的正则表达式为如果此弧不存在，则所求的正则表达式为。34图上作业法求下图所示的求下图所示的 DFA等价的等价的RE。预处理。预处理。35图上作业法预处理。预处理。去掉状态去掉状态 q3。36图上作业法去掉状态去掉状态 q3。去掉状态去掉状态 q4。37图上作业法去掉状态去掉状态q4。合并从标记为合并从标记为 q2的状态到标记为的状态到标记为Y 的状态的两条并行弧

26、。的状态的两条并行弧。38图上作业法合并从标记为合并从标记为 q2的状态到标记为的状态到标记为Y 的状态的两条并行弧。的状态的两条并行弧。去掉状态去掉状态 q0。11*039图上作业法去掉状态去掉状态 q0。并弧。并弧。11*040图上作业法并弧。并弧。去掉状态去掉状态 q1。41图上作业法去掉状态去掉状态 q1。去掉状态去掉状态 q2。1*0(11*0)*0(00*111*0+00*10+11*0)(11*0)*0)(00*+00*1)即即所求。所求。42图上作业法q几点值得注意的问题几点值得注意的问题(1)如果去状态的顺序不一样，则得到的如果去状态的顺序不一样，则得到的RE可能在形式是不一

27、样，但它们可能在形式是不一样，但它们都是等价的。都是等价的。(2)当当DFA的终止状态都是不可达的时候，状态转移图中必不存在从开始状的终止状态都是不可达的时候，状态转移图中必不存在从开始状态到终止状态的路。态到终止状态的路。此此时时，相，相应应的的RE为为。(3)不计算自身到自身的弧，如果状态不计算自身到自身的弧，如果状态q的入度为的入度为n，出度为，出度为m，则将状态，则将状态q及其相关的弧去掉之后，需要添加及其相关的弧去掉之后，需要添加n*m条新弧。条新弧。(4)对操作的步数施归纳，可以证明它的正确性。对操作的步数施归纳，可以证明它的正确性。推论推论4-1正则表达式与正则表达式与FA、正则

28、文法等价，是正则语言的表示模型。、正则文法等价，是正则语言的表示模型。434.4正则语言等价模型的总结正则语言等价模型的总结 DFARENFARG-NFA(q,a)=pqap(q,a)=pFqaAaBB(A,a)Aaqf(A,a)NFA(q,a)=-NFA(q,a)图上作业法图上作业法归纳归纳DFA(P,a)=NFA(P,a)44正则表达式的应用qUNIX中的正则表达式中的正则表达式q查找文本中的模式查找文本中的模式45UNIX 中的正则表达式q对正则表达式记号的第一项扩展是：处理对正则表达式记号的第一项扩展是：处理ASC字符集。字符集。qUNIX中的正则表达式允许书写字符类来尽可能紧凑地表示

29、大的字符集。中的正则表达式允许书写字符类来尽可能紧凑地表示大的字符集。字符类的规则是：字符类的规则是：(1)符号符号“.”(圆点圆点)表示任意字符。表示任意字符。(真正的小数点要用其它办法区分真正的小数点要用其它办法区分)(2)序列序列a1a2ak表示正则表达式表示正则表达式a1+a2+ak。(3)在方括号之内规定形如在方括号之内规定形如x-y的范围，表示的范围，表示ASC序列中从序列中从x到到y的所的所有字符。例如，有字符。例如，0-9,A-Z,A-Za-z0-9,-+0-9。(4)几种最常见的字符类有特殊记号。例如：几种最常见的字符类有特殊记号。例如：a):digit:表示十进制数字的集合

30、。表示十进制数字的集合。b):alpha:表示字母字符的集合。表示字母字符的集合。c):alnum:表示字母和数字字符的集合。表示字母和数字字符的集合。46UNIX 中的正则表达式q在在UNIX正则表达式中使用的运算符，这些运算符不扩大所表示的语正则表达式中使用的运算符，这些运算符不扩大所表示的语言范围，但有时更容易表达所要表达的内容。它们是：言范围，但有时更容易表达所要表达的内容。它们是：(1)用用 代替代替+来表示并。来表示并。(2)运算符运算符?表示表示“0个或个或1个个”。因此在。因此在UNIX中，中，R?与正则表达式的与正则表达式的+R是一样的。是一样的。(3)运算符运算符+表示表示

31、“1个或多个个或多个”。因此在。因此在UNIX中，中，R+与本书中的与本书中的正则表达式正则表达式RR*是一样的。是一样的。(4)运算符运算符n表示表示“n个副本个副本”。因此在因此在UNIX中，中，R5是是RRRRR的的缩写。缩写。47查找文本中的模式q假设要扫描非常大的假设要扫描非常大的Web页面并探测出个人或单位地址。可能只是想建页面并探测出个人或单位地址。可能只是想建立邮件地址表，或者也许是在尝试根据地点来对业务进行分类，使得系立邮件地址表，或者也许是在尝试根据地点来对业务进行分类，使得系统能够回答像统能够回答像“替我找一家在我目前位置需替我找一家在我目前位置需10分钟车程的饭馆分钟车

32、程的饭馆”这样的这样的模糊查询。模糊查询。q要解决的中心问题：什么样的字符串是街道的地址呢？要解决的中心问题：什么样的字符串是街道的地址呢？q首先，街道地址可能以首先，街道地址可能以“Street(大街大街)”或缩写或缩写“St.”来结尾。但是，来结尾。但是，有些人住在有些人住在“Avenue(大道大道)”或或“Road(大路大路)”上，这些也可能有缩写。上，这些也可能有缩写。因此，正则表达式的结尾可能类似于因此，正则表达式的结尾可能类似于Street St.Avenue Ave.Road Rd.48查找文本中的模式q像像Street这样的称乎前面必须有街道的名称。在英美等国家，这个名这样的称

33、乎前面必须有街道的名称。在英美等国家，这个名称通常是一个大写字母后跟着一些小写字母，可以用称通常是一个大写字母后跟着一些小写字母，可以用UNIX表达式表达式A-Za-z*来描述这个模式。来描述这个模式。q但是有些街道名称包含多个单词，比如美国华盛顿特区的但是有些街道名称包含多个单词，比如美国华盛顿特区的RhodeIslandAvenue（罗得岛大道）。因此，可以把街道名称的描述修订为：（罗得岛大道）。因此，可以把街道名称的描述修订为：A-Za-z*(A-Za-z*)*49查找文本中的模式q现在，要包括门牌号做为地址的一部分。大多数门牌号都是一个数字现在，要包括门牌号做为地址的一部分。大多数门牌

34、号都是一个数字串，但有些后面跟着一个字母，比如在串，但有些后面跟着一个字母，比如在“123AMainSt.”中就是这样。中就是这样。q表示门牌号的表达式表示门牌号的表达式0-9+A-Z？q表示街道地址的整个表达式是：表示街道地址的整个表达式是：0-9+A-Z？A-Za-z*(A-Za-z*)*(Street St.Avenue Ave.Road Rd.)50查找文本中的模式q如果让这个表达式来工作如果让这个表达式来工作,会得到很好的效果。但逐渐会发现还是遗漏会得到很好的效果。但逐渐会发现还是遗漏了一些情况了一些情况:街道可能不叫街道可能不叫Street（大街）（大街）,也不叫也不叫Avenue

35、（大道）或（大道）或Road（大（大路）路）,可能叫可能叫“Boulivard”，“Place”，“Way”及其缩写。及其缩写。街道名称可能完全是数字或是以数字开头，如街道名称可能完全是数字或是以数字开头，如42ndStreet（第（第42大大街）。街）。地址是邮政信箱或乡村投递路线。地址是邮政信箱或乡村投递路线。不以任何有不以任何有Street，Road意义的字样结尾。一个例子是美国硅谷的意义的字样结尾。一个例子是美国硅谷的EICaminoReal，作为西班牙语的作为西班牙语的“皇家大路皇家大路”，说，说“EICaminoRealRoad”是多余的，所以就需要是多余的，所以就需要处理像处理像

36、“2000EICaminoReal”这样的真实地址。这样的真实地址。还有一些暂时没有想到的地址形式。还有一些暂时没有想到的地址形式。q不管怎样，只要有一个正则表达式编译器，就能通过逐步修正地址的不管怎样，只要有一个正则表达式编译器，就能通过逐步修正地址的表示形式，来构造一个完整的地址识别器。这比不断修改用常规程序表示形式，来构造一个完整的地址识别器。这比不断修改用常规程序设计语言所写的代码，要容易得多。设计语言所写的代码，要容易得多。514.5小结小结(1)字母表字母表上的上的RE用来表示用来表示上的上的RL。,a(a)是是上的最基本的上的最基本的RE，它们分别表示语言，它们分别表示语言,a，

37、以此为基础，如果，以此为基础，如果r和和s分别是分别是上的表上的表示语言示语言R和和S的的RE，则，则r+s,rs,r*分别是分别是上的表示语言上的表示语言RS,RS,R*的的RE。如果。如果L(r)=L(s)，则称，则称r与与s等价。等价。(2)RE对对乘乘、加加满满足足结结合合律律；乘乘对对加加满满足足左左、右右分分配配律律；加加满满足足交交换换率率和和幂幂等率；等率；是加运算的零元素；是加运算的零元素；是乘运算的单位元；是乘运算的单位元；是乘运算的零元素。是乘运算的零元素。(3)RE是是RL的一种描述。容易根据的一种描述。容易根据RE构造出与它等价的构造出与它等价的FA。反过来，可。反过来，可以用图上作业法构造出与给定的以用图上作业法构造出与给定的DFA等价的等价的RE。(4)RL的的5种等价描述模型转换图。种等价描述模型转换图。52本章作业q1，2，5(1)(2)，6(1)