04 正则表达式

1形式语言与自动机朴秀峰[e-mail]2主要内容正则文法擅长语言的产生，有穷状态自动机擅长语言的识别。本章讨论正则语言的正则表达式描述。它在对正则语言的表达上具有特殊的优势，为正则语言的计算机处理提供了方便条件。简洁更接近语言的集合表示和语言的计算机表示等。主要内容典型RE的构造。与RE等价FA的构造方法。与DFA等价的RE的构造。34.1启示产生语言{anbmck|n,m,k≥1}∪{aicnbxam|i≥0,n≥1,m≥2,x为d和e组成的串}的正则文法为AaA|aB|cEBbB|bCCcC|cEcE|bFFdF|eF|aHHaH|a44.1启示计算集合set(q)set(A)={an|n≥0}={a}*set(B)=set(A){a}{bn|n≥0}={anabm|m,n≥0}={a}*{a}{b}*={a}+{b}*set(C)=set(B){b}{c}*={a}*{a}{b}*{b}{c}*={a}+{b}+{c}*set(D)=set(C){c}={a}+{b}+{c}*{c}={a}+{b}+{c}+54.1启示set(E)=set(A){c}{c}*={a}*{c}{c}*={a}*{c}+set(F)=set(E){b}{d,e}*={a}*{c}+{b}{d,e}*set(H)=set(F){a}{a}*={a}*{c}+{d,e}*{a}{a}*={a}*{c}+{d,e}*{a}+set(I)=set(H){a}={a}*{c}+{d,e}*{a}+{a}L(M)=set(D)∪set(H)={a}+{b}+{c}+∪{a}*{c}+{d,e}*{a}+{a}64.1启示根据集合运算的定义，{d,e}={d}∪{e}。从而，{d,e}*=({d}∪{e})*。这样可以将L(M)写成如下形式：L(M)={a}+{b}+{c}+∪{a}*{c}+({d}∪{e})*{a}+{a}记作：a+b+c++a*c+(d+e)*a+a=aa*bb*cc*+a*cc*(d+e)*aaa*74.2正则表达式的形式定义正则表达式(regularexpression，RE)设∑是一个字母表，(1)Φ是∑上的正则表达式，它表示语言Φ；(2)ε是∑上的正则表达式，它表示语言{ε}；(3)对于a∈∑，a是∑上的正则表达式，它表示语言{a}；(4)如果r和s分别是∑上表示语言R和S的RE，则：r与s的“和”(r+s)是∑上的RE，(r+s)表达的语言为R∪S；r与s的“乘积”(rs)是∑上的RE，(rs)表达的语言为RS；r的克林闭包(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)*))，表示语言{00}{00}*；(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字符串组成的语言。9约定(1)r的正闭包r+表示r与(r*)的乘积以及(r*)与r的乘积：r+=(r(r*))=((r*)r)(2)闭包运算的优先级最高，乘运算的优先级次之，加运算“+”的优先级最低。所以，在意义明确时，可以省略其中某些括号。((((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。相等也称为等价。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*)。(16)L((r*)*)=L(r*)。(17)L((r*s*)*)=L((r+s)*)。(18)如果L(r)L(s)，则r+s=s。12幂的定义幂r是字母表∑上的RE，r的n次幂定义为(1)r0=ε。(2)rn=rn-1r。基本结论(19)L(rn)=(L(r))n。(20)rnrm=rn+m。一般地，r+ε≠r，(rs)n≠rnsn，rs≠sr。13正则表达式举例设∑={0,1}00表示语言{00}；(0+1)*00(0+1)*表示所有的至少含两个连续0的0,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(0+1)*0))={x|x的开头字符与尾字符相同}。14举例构造一个正则表达式，使它能代表十进制正整数的集合。(1+2+3+4+5+6+7+8+9)(0+1+2+3+4+5+6+7+8+9)*构造一个正则表达式，使它能代表如下的集合S：S的每个元素都是倒数第十个字符是1的0、1串。(0+1)*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.3RE与FA等价正则表达式r称为与FAM等价，如果L(r)=L(M)。从开始状态出发，根据状态之间按照转移所确定的后继关系，依次计算出所给FA的各个状态q对应的set(q)，并且最终得到相应的FA接受的语言的RE表示。寻找一种比较“机械”的方法，使得计算机系统能够自动完成FA与RE之间的转换。16RE到FA的等价变换0对应的FA01对应的FA0+1对应的FA0*对应的FA17定理4-1定理4-1正则表达式表示的语言是正则语言。证明思路：施归纳于正则表达式中所含的运算符的个数n，证明对于字母表∑上的任意正则表达式r，存在FAM，使得L(M)=L(r)，并且M恰有一个终止状态。M在终止状态下不作任何移动。18定理4-1当n=0时，有如下3种情况：(1)r=ε(2)r=Φ(3)r=a19定理4-1假设结论对于n≤k时成立，则当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)。由于可以对状态进行重新命名，不妨设Q1∩Q2=Φ。20定理4-1(1)r=r1+r2q01M1f1q02M2f2fq0εεεεS取q0,fQ1∪Q2，令M=(Q1∪Q2∪{q0,f},∑,δ,q0,{f})①δ(q0,ε)={q01,q02}；②对q∈Q1-{f1}，a∈∑∪{ε},δ(q,a)=δ1(q,a);对q∈Q2-{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)。由归纳假设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)设x∈L(M1)∪L(M2)，从而有x∈L(M1)或者x∈L(M2)。22定理4-1当x∈L(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∈L(M)同理可证，当x∈L(M2)时，x∈L(M)。故L(M1)∪L(M2)L(M)。23定理4-1再证L(M)L(M1)∪L(M2)。设x∈L(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,ε)={f}进行的最后一次移动，注意到Q1∩Q2=Φ，则此时必有δ(q01,x)={f1}即x∈L(M1)。如果根据定义式δ(f2,ε)={f}进行的最后一次移动，注意到Q1∩Q2=Φ，则此时必有δ(q02,x)={f2}即x∈L(M2)。综上，x∈L(M1)∪L(M2)所以L(M)L(M1)∪L(M2)。综上所述，L(M)=L(M1)∪L(M2)。这说明M与r等价。25定理4-1q01M1f1q02M2f2εS(2)r=r1r2M=(Q1∪Q2,∑,δ,q01,{f2})①对q∈Q1-{f1}，a∈∑∪{ε}δ(q,a)=δ1(q,a)；②对q∈Q2，a∈∑∪{ε}δ(q,a)=δ2(q,a)；③δ(f1,ε)={q02}仅需证明L(M)=L(M1)L(M2)。26定理4-1(3)r=r1*q01M1f1fεεSq0εεεM=(Q1∪{q0,f},∑,δ,q0,{f})其中q0,fQ1，定义δ为①对q∈Q1-{f1}，a∈∑,δ(q,a)=δ1(q,a)。②δ(f1,ε)={q01,f}。③δ(q0,ε)={q01,f}。27定理4-1按照定理4-1证明给出的方法构造一个给定RE的等价FA时，该FA有可能含有许多的空移动。可以按照自己对给定RE的“理解”以及对FA的“理解”“直接地”构造出一个比较“简单”的FA。定理证明中所给的方法是机械的。由于“直接地”构造出的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)*等价的FA。εεεεS29定理4-1的举例按照对(0+1)*0+(00)*的“理解”“直接地”构造出的FA。30正则语言可以用正则表达式表示正则表达式表示的是正则语言。是否所有的正则语言都可以用正则表达式