资源描述
12024/6/17College of Computer Science&Technology,BUPT正则表达式与有限自动机的关系正则表达式与有限自动机的关系右线性语言与有限自动机的关系右线性语言与有限自动机的关系右线性语言的性质右线性语言的性质(part1)22024/6/17College of Computer Science&Technology,BUPT3.7 正则表达式与有限自动机的关系结论:有有限限自自动机机、右右（左左）线性性文文法法、正正则表表达式都定达式都定义了同一种了同一种语言言-正正则语言言.证明策略明策略 -NFANFADFARERE(Regular Expression)-正则表达式32024/6/17College of Computer Science&Technology,BUPT从从DFA 构造等价的构造等价的正则表达式正则表达式（状态消去法）（状态消去法）思路思路:(1)扩展自动机的概念，允许正则表达式作为转移弧的标记。这样，就有可能在消去某一中间状态时，保证自动机能够接受的字符串集合保持不变。(2)在消去某一中间状态时，与其相关的转移弧也将同时消去，所造成的影响将通过修改从每一个前趋状态到每一个后继状态的转移弧标记来弥补。以下分别介绍中间状态的消去与正则表达式构造过程。42024/6/17College of Computer Science&Technology,BUPT从从DFA 构造等价的构造等价的正则表达式正则表达式（中间状态的消去）（中间状态的消去）xy r1r2xz r1y r2代之以：xy r1+r2xyr2r1代之以：xy r1*xz y r1代之以：52024/6/17College of Computer Science&Technology,BUPT从从DFA 构造等价的构造等价的正则表达式正则表达式（中间状态的消去）（中间状态的消去）q1qkp1pmP1PmQkQ1R11R1mRkmRk1R11+Q1S*P1R1m+Q1S*PmRkm+QkS*PmRk1+QkS*P1q1p1qkpm消去消去s62024/6/17College of Computer Science&Technology,BUPT从从DFA 构造等价的构造等价的正则表达式正则表达式（状态消去法）（状态消去法）步骤步骤:(1)对对每每一一终终态态q，依依次次消消去去除除q 和和初初态态q0 之之外外的的其其它它状状态态;(2)若若q q0，最终可得到一般最终可得到一般形式如下左图形式如下左图的状态自动机，的状态自动机，该自动机对应的正则表达式可表示为该自动机对应的正则表达式可表示为 (R+SU*T)*SU*.(3)若若q=q0，最终可得到最终可得到如下右图的自动机，它对应的正则如下右图的自动机，它对应的正则 表达式可以表示为表达式可以表示为 R*.(4)最终最终的正则表达式为的正则表达式为每一终态对应的每一终态对应的正则表达式之和（并）正则表达式之和（并）.72024/6/17College of Computer Science&Technology,BUPT状态消去法举例状态消去法举例对于终态对于终态C对于终态对于终态D等价的正则表达式等价的正则表达式(0+1)*1(0+1)+(0+1)*1(0+1)(0+1)82024/6/17College of Computer Science&Technology,BUPT状态消去法举例状态消去法举例01342567 a b aa b b a b012567a+ba+b aabb0257(a+b)*(a+b)*aa+bb07(a+b)*(aa+bb)(a+b)*92024/6/17College of Computer Science&Technology,BUPT定定理理:L 是是正正则表表达达式式R 表表示示的的语言言,则存存在在一一个个 -NFA E,满足足L(E)=L(R)=L.证明明:构构造造性性证明明.可可以以通通过结构构归纳法法证明明从从R 可可以以构造出与其等价的，构造出与其等价的，满足如下条件的足如下条件的 -NFA：(1)恰好一个恰好一个终态;(2)没有弧没有弧进入初入初态；(3)没有弧离开没有弧离开终态；从从正则表达式正则表达式构造等价的构造等价的 -NFA102024/6/17College of Computer Science&Technology,BUPT基础基础:从从正则表达式正则表达式构造等价的构造等价的 -NFA（归纳归纳构造过程）构造过程）1 对于对于 ，构造构造为为 3 对于对于a，构造为构造为a2 对于对于 ，构造构造为为112024/6/17College of Computer Science&Technology,BUPT归纳归纳:从从正则表达式正则表达式构造等价的构造等价的 -NFA（归纳归纳构造过程）构造过程）1 对于对于R+S，构造为构造为 122024/6/17College of Computer Science&Technology,BUPT归纳归纳:从从正则表达式正则表达式构造等价的构造等价的 -NFA（归纳归纳构造过程）构造过程）2 对于对于RS，构造为构造为 3 对于对于R*，构造构造为为 132024/6/17College of Computer Science&Technology,BUPT举举例例:设设正正则则表表达达式式1*0(0+1)*,构构造造等等价价的的 -NFA.从从正则表达式正则表达式构造等价的构造等价的 -NFA0+1 1*142024/6/17College of Computer Science&Technology,BUPT从从正则表达式正则表达式构造等价的构造等价的 -NFA(0+1)*1*0(0+1)*152024/6/17College of Computer Science&Technology,BUPT3.8右线性语言与右线性语言与有限自动机有限自动机 至此，我们已学到正则集有三种定义方式，且这三种方式等价：1.正则集是含有，a以及在并、连接和*运算下封闭的语言2.由正规表达式定义的集合是正则集。3.由右线性文法生成的语言是正则集。此外，还有第四种方式：将正则集作为由有限自动机定义的集合。即正则集(右线性语言)有限自动机162024/6/17College of Computer Science&Technology,BUPT右线性文法右线性文法有限自动机有限自动机定定理理3.8.1：由任意右线性文法G定义的语言必然能被一个NFAM所接受。即L（G）L（M）证明思路（构造明思路（构造证明）明）：设右线性文法G（N，T，P，S），构造一个与G等价的有限自动机NFAM（Q，T，q0，F），其中：QNUH，H为一个新增加的状态,HN，q0SH，S当S-属于P。H否则的定的定义为：当当AaB P，则B（A，a）当当Aa P,则H（A，a）对于任意输入，（H，a）。F=172024/6/17College of Computer Science&Technology,BUPT右线性文法右线性文法有限自动机有限自动机（例）例：例：设有右有右线性文法性文法G=(S,B,a,b,P,S)，其中其中P：SaBBaB|bS|a试构造与构造与G等价的有限自等价的有限自动机机M。解：解：设NFAM=(Q,T,q0,F)Q=S,B,HT=a,bq0=SF=H转换函数函数：n对于于产生式生式SaB，有有(S,a)=Bn对于于产生式生式BaB，有有(B,a)=Bn对于于产生式生式BbS，有有(B,b)=Sn对于于产生式生式Ba，有有(B,a)=HSBH开始aaab182024/6/17College of Computer Science&Technology,BUPT右线性文法右线性文法有限自动机有限自动机（续）（续）求证求证G与与NFAM两者定两者定义了同一了同一语言。言。证明：明：先先证（1）文法）文法G产生的生的语言言L(G)能能够被被NFAM所接收；所接收；再再证（2）NFAM接受的接受的语言言L(M)可由文法可由文法G产生。生。192024/6/17College of Computer Science&Technology,BUPT右线性文法右线性文法有限自动机有限自动机（续）（续）证明方法：明方法：通过两者定义的语言中任意一个字符串来说明。（1）设=a1a2an L(G)，且n1则有Sa1A1a1a2A2a1a2an-1An-1a1a2an-1an则由的定义，有A1(S，a1)，A2(A1，a2),An-1(An-2，an-1)，H(An-1，an)，且H(S，)因为HF,所以被NFAM所接受。又若L（G）,则表明SP,由NFAM的定义，有SF,即也被NFAM接受。所以，由文法所以，由文法G派生的任意字符串派生的任意字符串 L（M）。#202024/6/17College of Computer Science&Technology,BUPT右线性文法右线性文法有限自动机有限自动机（续）（续）（2）再再证L(M)可由可由G产生生设=a1a2an被NFAM接受，即L（M），则必然存在状态序列S，A1，A2，An-1，H对M有转换函数为A1(S，a1)，A2(A1，a2),An-1(An-2，an-1)，H(An-1，an)则可规定G中含有产生式S a1A1，A1 a2A2，An-1 an于是存在推导Sa1A1a1a2A2a1a2an-1An-1a1a2an-1an即a1a2an是文法G的一个句子。也即也即 L（G）。）。#212024/6/17College of Computer Science&Technology,BUPT课堂练习：课堂练习：练习：设线性文法性文法G（S，A，B，a，b，P，S）P：SaA|baB|aAaA|aS|bBBbB|b|a构造相构造相应的的NFAM。222024/6/17College of Computer Science&Technology,BUPT有限自动机有限自动机右线性文法右线性文法定理定理3.8.2：设有限自有限自动机机M接受的接受的语言言为L(M)则存在右存在右线性文法性文法G，它它产生的生的语言言L(G)L(M)。证明思路：明思路：构造一个右构造一个右线性文法性文法G，使它接受由使它接受由NFAM定定义的的语言。言。构造方法：构造方法：设M（Q，T，q0，F），），构造一个右构造一个右线性文法性文法G（N，T，P，S），），其中其中NQ，Sq0P定定义为：若若（A，a）B且且BF，则AaB在在P中中若若（A，a）B且且BF，则Aa和和AaB在在P中中（注：（注：书上未明确）上未明确）L（M）L（G）的的证明明见书P91（自学）。自学）。232024/6/17College of Computer Science&Technology,BUPT有限自动机有限自动机右线性文法右线性文法（例）例：例：设有有DFAM=(q0,q1,q2,q3,a,b,q0,q3)其中其中转换函数如函数如图所示，所示，试构造与之等价的右构造与之等价的右线性文法性文法G。解：解：构造右构造右线性文法性文法G=(N,T,P,S)G=(N,T,P,S)N=q N=q0 0,q,q1 1,q,q2 2,q,q3 3 T=a,b S=q T=a,b S=q0 0 产生式集合生式集合P P(q0,a)=q1，q0aq1(q0,b)=q2，q0bq2(q1,a)=q3，q3F，q1a|aq3(q1,b)=q1，q1bq1(q2,a)=q2，q2aq2(q2,b)=q3，q3F，q2b|bq3q0q1q2q3aaabbb开始构造的文法构造的文法G(G(化化简q q3 3)：G=(qG=(q0 0,q,q1 1,q,q2 2,a,b,P,q,a,b,P,q0 0)P：q0aq0|bq2 q1a|bq1 q2aq2|b242024/6/17College of Computer Science&Technology,BUPT3.9右线性语言的性质右线性语言的性质主要内容：主要内容：DFA的极小化泵浦引理右线性语言的封闭性252024/6/17College of Computer Science&Technology,BUPT确定有限自动机确定有限自动机DFA的化简的化简(极小化极小化)对DFAM的极小化是找出一个状态数比M少的DFAM1，使满足L(M)=L(M1)1等价和可区分的概念设DFAM=(Q，T，q0，F)对不同的状态q，qQ和每个T*，如果有(q，)*(q，)必有(q，)*(q，)且qF，则称q与q状态等价.记为qq否则，称q，q可区分。262024/6/17College of Computer Science&Technology,BUPT确定有限自动机确定有限自动机DFA的化简的化简2不可达状态如果不存在任何T*，使(q，)*(q，)，则称状态qQ为不可达状态。3最小化若DFA不存在互为等价状态及不可达状态，则称DFA是最小化的。272024/6/17College of Computer Science&Technology,BUPT最小化算法最小化算法一个DFA的最小化，是把的状态集构成一个划分。即:任何两个子集的状态都是可区分的；同一子集中的任何两个状态都是等价的。之后，每个子集用一个状态代表，并取一个状态名。构成划分的步构成划分的步骤:1.构成基本划分=，”，(为终态集，”为非终态集)2.细分=1，2，n，ii=q，q，q当输入任意字符a时，若i中的状态经标a的边可到达的状态集的元素分属于两个不同的子集中，则将i细分为两个子集.重复步骤(2)，直至不可再细分，得到1.若1中有不可达状态，将其删除，1便是最小化的.282024/6/17College of Computer Science&Technology,BUPT例例(1)q，q为不可达状态，删除之.(2)Q=q，q，q，q，q,=q，q，q，q，q构成基本划分=，”(a)对于=q，q，对字符a，有(q，a)=q，(q，a)=qq，q同一子集.对字符b，有(q，b)=q，(q，a)=qq，q同一子集.=q，q不能再细分.可用q表示状态.(b)对于”=q，q，q对a，(q,a)=q，(q,a)=q，(q,a)=qq,q同一子集对b，(q,b)=q，(q,b)=q，(q,b)=qq，q，q同一子集.将再分解.=q，q1，q3，q1，q3不可再细分，用q1表示q，q，q292024/6/17College of Computer Science&Technology,BUPT计算状态集划分的算法计算状态集划分的算法填表法填表法填表算法（填表算法（table-filling algorithm）基于如下递归地基于如下递归地标记可区别的状态偶对的过程标记可区别的状态偶对的过程:-基础基础如果如果p 为终态，而为终态，而q 为非终态，则为非终态，则p 和和q 标标记记为可区别的；为可区别的；-归纳归纳设设p 和和q 已标记为可区别的已标记为可区别的,如果状态如果状态r 和和s 通过某个通过某个输入符号输入符号a 可分别转移到可分别转移到p 和和q，即即(r,a)=p,(s,a)=q,则则r 和和s 也标记为可区别的；也标记为可区别的；这是因为：这是因为：若若p 和和q 可为字符串可为字符串w 区别区别,则则r 和和s 可可为字符串为字符串aw 区别区别.（(r,aw)=(p,w),(s,aw)=(q,w)）302024/6/17College of Computer Science&Technology,BUPT计算状态集划分的算法计算状态集划分的算法填表法填表法填表算法举例填表算法举例xxxxxxxxxxxxx(1)区别所有终态和非终态区别所有终态和非终态(2)区别区别(1,3),(1,4),(2,3),(2,4),(5,6),(5,7)xxxxx(3)区别区别(3,4)x(4)结束结束.划分结果：划分结果：1,2,3,4,5,6,7312024/6/17College of Computer Science&Technology,BUPT通过合并等价的状态进行通过合并等价的状态进行DFA 的优化的优化步骤步骤1.删除所有从开始状态不可到达的状态及与其相关的边删除所有从开始状态不可到达的状态及与其相关的边,设所得到的设所得到的DFA为为A=(Q,T,q0,F)；2.使用填表算法找出所有等价的状态偶对；使用填表算法找出所有等价的状态偶对；3.根据根据2 的结果计算当前状态集合的划分块，每一划分的结果计算当前状态集合的划分块，每一划分块中的状态相互之间等价，而不同划分块中的状态之块中的状态相互之间等价，而不同划分块中的状态之间都是可区别的间都是可区别的.包含状态包含状态q 的划分块用的划分块用q 表示表示.4.构造与构造与A 等价的等价的DFAB=(QB,T,B,q0,FB),其中其中QB=q|q Q,FB=q|q F,B(q,a)=(q,a)322024/6/17College of Computer Science&Technology,BUPT通过合并等价的状态进行通过合并等价的状态进行DFA 的优化的优化举例举例划分结果：划分结果：1,2,3,4,5,6,7 等价的状态偶对为：等价的状态偶对为：（1,2）,（6,7）新的状态集合：新的状态集合：1,3,4,5,6332024/6/17College of Computer Science&Technology,BUPT最小化的最小化的DFA课堂练习课堂练习最小化下列最小化下列DFA:参考结果参考结果342024/6/17College of Computer Science&Technology,BUPT针对正则语言的针对正则语言的Pumping 引理引理正则语言应满足的一个必要条件用于判定给定的语言不是正则集。物物理理意意义：当给定一个正则集和该集合上一个足够长的字符串时，在该字符串中能找到一个非空的子串，并使子串重复，从而组成新的字符串。该新串必在同一个正则集内。定理：定理：设L是正则集，存在常数k，对字符串且，则可写成10，其中10，0，对所有的0有10i2。证明证明 设设L 是是DFA D=(Q,T,q0,F)的语言，的语言，取取k=|Q|即即可可.352024/6/17College of Computer Science&Technology,BUPTDFA的的“Pumping”特性特性设DFA D=(Q,T,q0,F),|Q|=n.对于任一长度不小于n 的字符串w=a1a2am,其中mn,akT(1 k m),qQ,考察如下状态序列 p0=q p1=(q,a1)p2=(q,a1a2)pn=(q,a1a2an)pn+1=(q,a1a2an+1)pm=(q,a1a2am)由pigeonhole 原理,p0,p1,p2,pn 中至少有两个状态是重复的，即存在i,j,0ijn,pi=pj.“pumping”特性：任一长度不小于状态数目 的字符串所标记的路径上，必然出现重复的状态.362024/6/17College of Computer Science&Technology,BUPTDFA的的“Pumping”特性特性“pumping”特性：特性：如前如前,设设DFA D=(Q,T,q0,F),|Q|=n,w=a1a2am(m n),则存在则存在i,j,0 i j n,pi=pj,其中其中pk=(p0,a1a2ak),0 k m.若假定若假定p0=q0,pm F,即即w L(D).令令w=xyz,其中：其中：x=a1a2ai,y=ai+1ai+2aj,z=aj+1aj+2am 则对任何则对任何k 0，都有都有xykz L(D).(参考下图参考下图)p0pipmx=a1a2aiy=ai+1ai+2ajz=aj+1aj+2am372024/6/17College of Computer Science&Technology,BUPTPumping 引理的应用引理的应用（用于用于证明某个明某个语言言L 不是正不是正规语言）言）证明步明步骤 1.选任意的任意的n.2.找到一个找到一个满足以下条件的串足以下条件的串w L(长度至少度至少为n).3.任任选满足足w=xyz y|xy|n的的x,y,z 4.找到一个找到一个k 0,使使xykz L.举例举例证明明L=anbn|n1不是正不是正则集集.证明明:由由泵浦引理，假浦引理，假设L是正是正则集，集，则对足足够大的大的n，anbn可写成可写成102，其中其中0n0中不可能含中不可能含b+，否，否则不不满足足0|10|n.0只可能取只可能取a+，设|0|=k1，k为常数，常数，取取i=0，有有1002=12=an-kbn，此此时，a，b字字符符个个数数不不同同,即新即新组成的串成的串12 L.与假与假设矛盾，故矛盾，故L不是正不是正则集集.382024/6/17College of Computer Science&Technology,BUPTPumping 引理的应用引理的应用 例例 证明证明kk的整数不是正则集的整数不是正则集.证明证明假设假设L是正则集，取足够大的整数是正则集，取足够大的整数n，.有有102=n2n，00n，010n取取i=2，有有n21022n2+n(n+1)2 10i2(串长不是整数的平方串长不是整数的平方)与假设矛盾。与假设矛盾。L不是正则集。不是正则集。392024/6/17College of Computer Science&Technology,BUPT课后练习课后练习 转换下列正下列正则表达式表达式为带 转移的移的NFANFA.a)01*.b)(0+1)01.c)00(0+1)*.Chap3 习题5，7，17
展开阅读全文