正则表达式.ppt

文档介绍：*形式语言与自动机朴秀峰xfpiao@*主要内容正则文法擅长语言的产生,有穷状态自动机擅长语言的识别。本章讨论正则语言的正则表达式描述。它在对正则语言的表达上具有特殊的优势,为正则语言的计算机处理提供了方便条件。简洁更接近语言的集合表示和语言的计算机表示等。主要内容典型RE的构造。与RE等价FA的构造方法。与DFA等价的RE的构造。*{anbmck|n,m,k≥1}∪{bxam|i≥0,n≥1,m≥2,x为d和e组成的串}的正则文法为AaA|aB|cEBbB||cEcE|bFFdF|eF|aHHaH|a*(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}+*(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}*,{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**+*(d+e)*aaa**(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)的表达式才是∑上的正则表达式。*正则表达式举例设∑={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字符串组成的语言。*约定(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。 相等也称为等价。*基本结论(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}。