形式语言与自动机理论-03

第3章正则表达式与正则语言西北工业大学计算机学院康慕宁启示在前面我们已经用到了一些类似正则表达式来表示语言：–L(G)={0n|n≥1}–L(G)={anbn|n≥1}–L(G)={0n1m2k|n,m,k≥1}这种表示法的优点：–比文法和有穷状态自动机简单；–更接近集合表示和计算机表示。正则表达式的形式定义定义：设Σ是一个字母表，那么(1)φ是Σ上的正则表达式(regularexpression,简记为RE)，它表示语言φ。(2)ε是Σ上的RE，它表示语言{ε}。(3)对于∀a∈Σ，a是Σ上的RE，它表示语言{a}。(4)如果r和s分别是Σ上表示语言R和S的RE，则r与s的“和”:(r)+(s)是Σ上的RE，表达的语言为R∪S。r与s的“乘积”:(r)·(s)是Σ上的RE，表达的语言为RS。r的克林闭包:(r)*是Σ上的RE，表达的语言为R*。(5)只有有限使用规则(1)-(4)所得的表达式才是Σ上的RE。RE举例设Σ={0,1}，下面是Σ上的RE：(1)φ，表示语言φ。(2)ε，表示语言{ε}。(3)0，表示语言{0}。(4)1，表示语言{1}。(5)(0+1)，表示语言{0,1}。(6)(01)，表示语言{01}。(7)((0+1)*)，表示语言{0,1}*。(8)((01)(01)*)，表示语言{01}{01}*。(9)((((0+1)*)000)((0+1)*))，表示至少含有3个连续0的串组成的语言。(10)((((0+1)*)0)1)，表示所有以01结尾的字符串组成的语言。(11)(1(((0+1)*)0))，表示所有以1开头以0结尾的字符串组成的语言。运算优先级上面的例子中，正则表达式中所含扩号太多，带来准确性和许多麻烦。为了省去这些扩号，需要约定正则表达式中运算的优先级。闭包运算的优先级最高，乘运算的优先级次之，加运算的优先级最低。加、乘、闭包运算均执行左结合规则。“·”运算在不影响顺序情况下，可省略例如：–((((0+1)*)0·0·0)·((0+1)*))＝(0+1)*000(0+1)*–((((0+1)*)·0)·1)＝(0+1)*01–(1·(((0+1)*)·0))＝1(0+1)*0正则表达式的等价正则表达式表示的语言：在意义明确时，正则表达式r表示的语言记为L(r)或Lr。设r,s是字母表Σ上的正则表达式，如果L(r)=L(s)，则r称为与s相等(equivalence，也称为等价)，记作r=s。例如：(0+1)*(0+1)(0+1)*=(0+1)(0+1)*，因为它们表示的语言都是{0,1}+。正则表达式运算定律可以证明，对字母表Σ上的正则表达式r,s,t，下列各式成立：(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,注意rs≠sr(4)幂等律：r+r=r,注意rr≠r(5)加法运算零元素：r+φ=r,注意不是r+ε=r(6)乘法运算单位元：rε=εr=r(7)乘法运算零元素：rφ=φr=φ(8)L(φ)=φ(9)L(ε)={ε}(10)L(a)={a}(11)L(rs)=L(r)L(s)正则表达式运算定律(2)(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。幂的定义正则表达式到FA的等价变换思路：–正则表达式是以递归的形式定义的，包括三种基础(φ,ε,a)与三种运算符(加,乘,克林闭包)。任何一个正则表达式都可以看作是基础经过若干运算产生的。–因此，可以对正则表达式中所含运算符个数施归纳。首先对三种基础表达式都给出等价的FA，然后为每种运算构造等价的FA。–为了构造FA方便起见，对于构造的FA进行一些限制：有且只有一个终止状态，而且在终止状态下不做任何移动。正则表达式到FA的等价变换-举例正则语言可以用正则表达式表示注意，q1为初态含义：从状态i到状态j不经过下标大于k的状态的所有字符串之集＝从状态i到状态j不经过下标大于k－1的状态的所有字符串集合与从状态i到k不经过大于k-1的字符串连接若干从k到k不经过大于k-1的字符串，再连接从k到j不经过大于k-1的字符串的集合之并。正则语言可以用正则表达式表示正则语言可以用正则表达式表示图上作业法——说明(1)如果去状态的顺序不一样，则得到的正规表达式可能在形式上不一样，但都是等价的。(2)当DFA的终止状态都是不可达的时候，状态转移图中肯定不存在从开始状态到终止状态的路。相应的正规表达式为φ。(3)若不计算自身到自身的弧，如果状态q的入度为n，出度为m，则将状态q及其相关的弧去掉之后，需添加nm条新弧。(4)对操作的步数施归纳，可以证明图上作业的正确性。(5)按照所给方法，不会将标记为X和Y的状态去掉。正则语言正则表达式和正则文法适于人理解、处理和交流。有限状态自动机适合计算机处理。用DFA的完备性来验证模型的完备性。正则语言应用编译器中的字法分析器命名规则以正则表达式给出分析时用有限状态自动机识别模式匹配字符串快速查找符合特定模式的字符串快速查找协议、程序等模型的完备性验证将要验证的问题描述为有限状态自动机模型看所有状态对所有输入是否都有处理RE的用途Regularexpressionsareusedine.g.1.UNIXgrepcommand2.UNIXLex(Lexicalanalyzergenerator)andFlex(FastLex)tools.