有限自动机理论-4章正则语言.ppt

《有限自动机理论-4章正则语言.ppt》由会员分享，可在线阅读，更多相关《有限自动机理论-4章正则语言.ppt（134页珍藏版）》请在三一办公上搜索。

1、第四章 正则语言,正则表达式RE与有限状态自动机DFA(或NFA)是等价的。一个语言L，如果能够被有限状态自动机所接收，则一定存在着对应的正则表达式来代表该语言(该语言就是正则集)；,一个语言L，如果能够被正则表达式来表示，则一定存在着对应的有限状态自动机，能够接收该语言(该语言就是FSL)；每个FSL都是正则集。,右线性语言，正则集和FSL是等价的，只不过是从不同的角度来对语言进行的描述：右线性文法产生右线性语言；通过运算得到正则集；有限状态自动机DFA(或NFA)接收FSL。正则表达式表示正则语言。,4.1 正则语言与有限状态自动机,4.1.1 正则表达式与有限状态自动机可以直接构造有限状

2、态自动机NFA接收正则表达式表示的正则语言。,例4-1 简单的正则表达式和对应的有限状态自动机的情况。P87,正则表达式0对应的NFA:正则表达式01对应的NFA:,正则表达式0+1对应的NFA:,或构造仅有一个接收状态的带-NFA:,正则表达式0*对应的有限状态自动机:,对于比较复杂的正则表达式，如何得到所对应的有限状态自动机?,定理4-1,设r是一个正则表达式，则存在一个带动作的有限状态自动机，有L(NFA)=S(r)。,证明:,对于正则表达式r中三种运算(连接、联合和迭代)的数目n作归纳证明:,对于正则表达式r，存在一个等价的-NFA;该-NFA只有一个接收状态,且没有从该接收状态出发的

3、任何状态转换。,归纳基础：,设正则表达式r的构造次数n为0，即r没有经过任何运算(连接、联合和迭代)而得，因此，r只能为、或者是字母表中的某个元素a。1)r=2)r=3)r=a所以，结论对于n=0成立；,归纳步骤：,假设结论对nk(k0)成立，则当n=k+1，根据r最后一次运算的形式，分为三种情况：,1)r=r1+r2 r1和r2中所含的运算符的个数不会大于k，根据归纳假设，存在满足定理要求的-NFA。,M1=(Q1，1，1，q1，f1)和M2=(Q2，2，2，q2，f2)且L(M1)=S(r1)；L(M2)=S(r2),假设Q1和Q2不相交，设置Q=Q1UQ2Uq0,f0,=1U2构造-NF

4、A=(Q,q0，f0),其中函数为：,(q0，)=q1，q2对于qQ1-f1，a1U，(q，a)=1(q，a)；对于qQ2-f2，a2U，(q，a)=2(q，a)；,(f1，)=f0(f2，)=f0,对于构造出的-NFA，可以形象地表示:,该-NFA包括了原来M1和M2的所有函数，增加了4个扫描的函数，使得：从-NFA的开始状态出发，通过两个动作，可以选择地到达M1或M2的开始状态q1或q2，然后，使用M1或M2的自己的函数，到达M1或M2的惟一接收状态f1或f2，最后，进入NFA的惟一接收状态f0。,显然，-NFA接收的语言是L(M1)和L(M2)的联合，即r=r1+r2。,2)r=r1r2

5、 r1和r2中所含的运算符的个数不会大于k，根据归纳假设，存在满足定理要求的-NFA：,M1=(Q1，1，1，q1，f1)和M2=(Q2，2，2，q2，f2)且L(M1)=S(r1)，L(M2)=S(r2),假设Q1和Q2不相交，现构造-NFA=(Q1UQ2，1U2,q1，f2),其中函数为,对于qQ1-f1，a1U(q，a)=1(q，a)；(f1，)=q2对于qQ2-f2，a2U，(q，a)=2(q，a)；,对于构造出的-NFA，可以形象地表示：,该-NFA包括了原来M1和M2的所有函数，增加了1个扫描的函数，使得：,-NFA从M1的开始状态q1出发，使用M1自己的函数，到达M1的惟一接收状

6、态f1，使用新增加的函数(f1，)=q2，到达M2的开始状态q2，然后，使用M2自己的函数，到达M2的惟一接收状态f2(也是构造的-NFA的惟一接收状态)。,显然，-NFA接收的语言是L(M1)和L(M2)的连接，即r=r1r2。,3)r=r1*r1中所含的运算符的个数不会大于k，根据归纳假设，存在满足定理要求的-NFA：,M1=(Q1，1，1，q1，f1)使得：L(M1)=S(r1),设置Q=Q1Uq0,f0,构造-NFA=(Q，1，q0，f0),其中函数为：,(q0，)=q1，f0 对于qQ1-f1，a1U(q，a)=1(q，a)；(f1，)=q0，f0,对于构造出的-NFA，可以形象地表

7、示：,该-NFA包括了原来M1的所有函数，增加了4个扫描的函数，使得：,从-NFA的开始状态出发，通过两个动作，可以直接进入NFA的惟一接收状态f0(以便能够接收空串)；或者到达M1的开始状态q1，然后，从M1的开始状态q1出发，使用M1自己的函数，到达M1的惟一接收状态f1，,通过两个动作，可以直接进入-NFA的接收状态f0，以便结束接收过程；也可以再将状态转换为M1的开始状态q1，以便迭代地接收输入串。,显然，-NFA接收的语言是L(M1)的闭包，即r=r1*。,根据r最后一次运算的三种情况，可知，当n=k+1，结论也成立。,对于正则表达式r，存在一个等价的-NFA，该-NFA只有一个接收

8、状态,且没有从该接收状态出发的任何状态转换。,该定理也说明了正则语言对于联合、连接和闭包三种运算是封闭的。,例4-2,为正则表达式10*+0构造等价的NFA。分析：根据运算符的优先级，正则表达式10*+0实际上为：（1（0*）+0,是r1+r2（联合）的形式；其中：r1=10*，r2=0；r1可以表示为r3r4的形式；其中：r3=1，r4=0*；,可以简化为无的NFA,定理4-2,如果语言L被一个DFA所接收，则语言L可以用一个正则表达式来表示。证明：设语言L被DFA=(Q，q1，F)所接收；,状态集合Q中有n个状态，按任意顺序进行编号；即Q=q1，q2，q3，qn。使用记号Rijk代表字符串

9、的集合，具体定义为：,Rijk=w|*(qi，w)=qj，且对于w的任何前缀x(xw，x)，如果*(qi，x)=ql，则lk,Rijk是所有那些将DFA从给定状态qi引导到状态qj，并且中间不经过（进入并离开）编号大于k的任何状态的所有字符串的集合，,要注意的是，i，j的大小与k的大小无关；显然，Rijn是所有那些将DFA从给定状态qi引导到状态qj的字符串的集合。,根据定义，可以得出如下的递推公式：a|(qi，a)=qj 若ijRij0=a|(qi，a)=qjU 若i=j,Rijk=Rikk-1(Rkkk-1)*Rkjk-1URijk-1(k=1,2,3,n),输入串w使DFA由状态qi到状

10、态qj，且中间不经过编号大于k的任何状态，只可能有两种情况：,(1)w在Rijk-1中，即中间不经过编号大于等于k（不超过k-1）的任何状态；(2)在由状态qi到状态qj的过程中，中间可能经过一个或者多个qk状态，即状态变化序列呈下述形式qiqkqkqkqj其中：在处出现的状态的编号均小于k；,从qiqk读过的w的子串属于Rikk-1，从qkqkqk读过的w的子串属于(Rkkk-1)*，从qkqj读过的w的子串属于Rkjk-1。现在证明，对于任何Rijk，存在正则表达式rijk能代表的Rijk，可采用对k的归纳法进行证明。,归纳基础：,k=0时，因为 a|(qi，a)=qj 若ijRij0=a

11、|(qi，a)=qjU 若i=j即Rij0是一个有穷集，其中每个元素，或是中的元素或是。,Rij0=a1+a2+ap 若ij 或Rij0=a1+a2+ap+若i=j 其中a1，a2，ap是使(qi，a)=qj的一切字母a的集合。,归纳步骤：,假设对lk的l，Rijl，都已经求出对应的正则表达式rijl代表Rijl，现考虑l=k，根据递推公式，存在正则表达式rijk=rikk-1(rkkk-1)*rkjk-1Urijk-1代表Rijk。,设DFA的接收状态集合F=qj1，qj2，qj3，qjp，因为q1是开始状态，qj是接收状态之一，R1jn表示状态q1到状态qj且中间不经过编号大于n的状态（因

12、为n是状态最大的编号，也就是说，对于中间经过的状态不加任何限制）所读过的字符串的集合，则,该DFA接收的语言对应的正则表达式为：r1j1n+r1j2n+r1jpn即 L（DFA）=R1j1nUR1j2nUUR1jpn=UR1fn qfF所以，对于任何Rijk，存在正则表达式rijk能代表的Rijk。证毕。,例4-3对于给定的DFA，给出对应的正则表达式。,k=0 k=1 k=2,r11k(00)*r12k 0 0 0(00)*r13k 1 1 0*1r21k 0 0 0(00)*r22k+00(00)*r23k 1 1+01 0*1r31k(0+1)(00)*0r32k 0+1 0+1(0+1

13、)(00)*r33k+(0+1)0*1,其中某些正则表达式已经被化简；例如r221=r210(r110)*r120+r220=0()*0+,可以化简为00+；,又例如r132=r121(r221)*r231+r131=0(+00)*(1+01)+1,由于(+00)*可以化简为(00)*，(1+01)可以化简为(+0)1，则r132=0(00)*(+0)1+1由于(00)*(+0)可以化简为0*,于是,r132=00*1+1=0*1,由于L(DFA)=R123UR133,所以,代表该语言的正则表达式为r123+r133,则r123=r132(r332)*r322+r122=0*1(+(0+1)0

14、*1)*(0+1)(00)*+0(00)*=0*1(0+1)0*1)*(0+1)(00)*+0(00)*,r133=r132(r332)*r332+r132=0*1(+(0+1)0*1)*(+(0+1)0*1)+0*1=0*1(0+1)0*1)*(+(0+1)0*1)+0*1=0*1(0+1)0*1)*D+(0+1)0*1)*(0+1)0*1)+)=0*1(0+1)0*1)*,因此 r123+r133=0*1(0+1)0*1)*(0+1)(00)*+0(00)*+0*1(0+1)0*1)*=0*1(0+1)0*1)*(0+1)(00)*+)+0(00)*,使用上述方法求一个DFA接收语言的正则

15、表达式对于计算机系统而言是比较容易的,而如果需要“人为”地来进行，还是比较烦琐的，下面介绍一种“图上作业”的方法，顾名思义，这种方法是通过对DFA的状态转换图的处理来直接获取等价的正则表达式的方法。,在这里，放宽对DFA的状态转换图的弧标记的限制，允许弧上的标记可以直接是字母表上的正则表达式。下面，给出一些基本的替换。,由于DFA的开始状态的入度不一定为0(即其他状态可以接收某个字母后，DFA的状态可以转换为开始状态)，而且DFA的接收状态也可能不止一个，所以，需要先对DFA的状态转换图进行适当的处理：,增加标记为X和Y的两个状态：X状态为新的开始状态，且入度为0；Y状态是新的惟一接收状态；然

16、后，对状态图进行响应的处理，直到整个图最后只剩下X和Y的两个状态，,以及从X状态到Y状态的可能的惟一一条弧；而这条弧上标记的正则表达式，就是所求的DFA所接收语言对应的正则表达式。当该弧不存在时，DFA所接收语言为，对应的正则表达式为。,具体的对于DFA=(Q，q0，F)的状态转换图进行处理的步骤为：,(1)预处理,增加标记为X和Y的两个状态 增加标记为X和Y的两个状态，从X状态到原来的开始状态q0引入一条弧，标记为，使得X状态为新的开始状态；从每一个接收状态引一条弧到Y状态，每条弧都分别标记为，使得Y状态为新的惟一接收状态。,(1)预处理,去掉所有的不可到达状态。,(2)对已经经过预处理的D

17、FA的状态转换图重复如下的操作，直到该图中仅仅只剩下X和Y两个状态，并且这两个状态之间最多只有一条弧。,并弧 对图中任意两个状态q和p，如果图中包含有从q到p的标记为r1，r2，r3，rg的并行的弧，则可以使用标记为r1+r2+r3+rg的弧取代这g个并行的弧，其中，状态q和p可以是不同的两个状态，也可以是相一个状态。,去状态1 对图中任意三个状态q、p和t，如果从q到p有一条标记为r1的弧，从p到t有一条标记为r2的弧，并且不存在从状态p出发的其他的弧，就可以将状态p去掉，并将与状态p相关联的两条弧去掉，使用一条从状态q到t标记为r1r2的弧来代替。,去状态2 对图中任意三个状态q、p和t，

18、如果从q到p有一条标记为r1的弧，从p到t有一条标记为r2的弧，并且存在从状态p到状态p本身标记为r3的弧，就可以将状态p去掉，并将与状态p相关联的三条弧都去掉，使用一条从状态q到t标记为r1r3*r2的弧来代替。,去状态3 如果状态图中只剩下3个状态，而且不存在从X状态到Y状态的路，则可以将X状态和Y状态之外的第3个状态以及与第3个状态相关的所有弧都删除掉。,(3)X状态到Y状态的弧上所标记的正则表达式就是原来DFA所接收语言对应的正则表达式。如果从X状态到Y状态并不存在弧，则对应的正则表达式为。,例4-4 求DFA所接收语言对应的正则表达式。,执行步骤1（预处理），,去掉状态q3,去掉状态

19、q4,合并从状态q2到状态Y的两条弧,去掉状态q0,合并状态q1的弧,去掉状态q1,去掉状态q2,则得1*0(11*0)*0(00*111*0+00*10+11*0)(11*0)*0)*（00*1+00*）,在使用“图上作业”方法时，以下几点需要注意：,如果删除状态的顺序不一致，最后得到的正则表达式可能在形式上不一样，但它们都是等价的；而且删除状态和并弧操作也没有绝对的先后顺序，一般地，在状态图的处理过程中，优先地执行并弧操作，会使后继的删除状态简单一些，因为增加的弧会少一些。,当DFA的接收状态都是不可到达状态时，状态转换图中肯定不存在从开始状态到某个接收状态的路；使用“图上作业”方法，最终

20、会去掉除状态X和状态Y以外的所有状态和弧，这种情况下，对应的正则表达式为。,不计算自身到自身的弧，如果状态q的入度为n，出度为m，则将状态q及相关的弧去掉之后，需要增加n*m条新弧。对于操作步骤进行归纳假设，不难证明“图上作业”方法的正确性。按照“图上作业”的方法，最后，将标记为X和Y的两个状态去掉，即得所需要的正则表达式。,“图上作业”的方法，也可以当作一个算法，可以利用计算机实现，有兴趣的读者可以进行试验。,4.1.2 正则语言的等价模型,正则语言有5种等价模型：正则文法(右线性文法)RG，正则表达式RE、确定的有限状态自动机DFA，不确定的有限状态自动机NFA，带动作的有限状态自动机-N

21、FA。正则语言的5种等价模型的转换关系可以用图4-28表示。,5种等价模型之间的（直接）转换,1)DFA 转换为RG2)RG转换为NFA3)NFA转换为RE4)RE转换为-NFA5)-NFA转换为NFA6)NFA转换为DFA,4.2 正则语言的泵浦引理,任何有穷语言都是正则语言，所以，任何非正则语言都肯定是无穷语言。需要讨论的就是无穷语言是否为正则的语言。,有限状态自动机时识别正则语言的模型。一个有限状态自动机只有有限个状态；这就是说，当该有限状态自动机识别的语言L是有穷语言时，可以构造足够多的接收状态，每个接收状态对应识别语言L中的一个字符串(如果状态q0，q1，q2，qm中没有相同的状态，

22、则m+1个状态接收的字符串仅有m个字符)。,当该有限状态自动机识别的语言L是无穷语言时，语言L必定存在一个足够长的句子，使得有限状态自动机在识别该句子的过程中，必定要重复地经过某一个状态，即在该有限状态自动机的状态转换图中存在着回路(循环)。,如果语言L的足够长的某个句子为z=a1a2a3am，假设有限状态自动机在识别它的过程中，需要经过的状态依次为q0，q1，q2，qm。,根据鸽笼原理,当m大于等于有限状态自动机的所有可达状态的个数时，这些状态中至少有一对是重复出现的，例如，qk和qj是同一状态；其中：kj。如果v=ak+1ak+2aj 是引导有限状态自动机从状态qk到状态qj的子串，则它就

23、是该有限状态自动机的状态转换图中从状态q0到状态qm的标记为w的路中从状态qk到状态qj的标记为v的回路，因此，v在它出现的位置无论重复出现多少次，所构成的字符串都一定是该有限状态自动机所识别的句子。,由于qk和qj是同一状态，为方便理解，将图改造。,根据鸽笼原理，这样的qk和qj状态在有限状态自动机的状态序列q0，q1，qN中是一定存在的，其中：N是有限状态自动机所包含的状态的个数。,此时有：(q0,a1a2ak)=qk，(qk,ak+1aj)=qj，(qj,aj+1am)=qm，qmF对于任意整数i0，有：(q0,a1ak(ak+1aj)iaj+1am)=qm，即a1ak(ak+1aj)i

24、aj+1am)L(M)取u=a1a2ak，v=ak+1aj，w=aj+1am，那么有：uviwL，|uv|N，|v|1,下面给出这种情况严格的描述，并给出判定一个语言不是正则语言的一般方法。设语言L是一个正则的语言，有限状态自动机M=(Q，q，F)满足 L=L(M),不失一般性，设状态集合Q中不含任何不可到达的状态，且|Q|=N。取语言L的句子z=a1a2a3am(mN)对于整数h，1hm，令*(q0，a1a2a3ah)=qh由于mN，所以，在状态序列q0，q1，qN中至少有两个状态是相同的；假设这两个状态为qk和qj，,即qk=qj；且kjN；此时有*(q0，a1a2a3ak)=qk*(qk

25、，ak+1ak+2aj)=qj=qk*(qj，aj+1aj+2am)=qm,注意到qj=qk，所有对于任意的整数i0，*(qk,(ak+1ak+2aj)i)=*(qk,(ak+1ak+2aj)i-1)=*(qk,(ak+1ak+2aj)i-2)=*(qk,ak+1ak+2aj)=qk,因为，zL(M)所以，qmF故，对于任意的整数i0，*(q0，a1a2ak(ak+1ak+2aj)i-1ajaj+1am)=qm也就是说，a1a2ak(ak+1ak+2aj)i-1ajaj+1amL(M),取 u=a1a2ak v=ak+1ak+2aj w=ajaj+1am于是，uvwL(M)对于任意的整数i0，

26、uviwL(M),注意到kN和kj，所以，u和v满足下面的条件：|uv|N 且|v|1。根据讨论的有限状态自动机的任意性，得到下面的引理。,引理4-5 正则语言的泵浦引理,设语言L为一个正则语言，则存在仅依赖与语言L的正整数N，对于语言L中的串z，如果|z|N，则存在u，v，w，满足：z=uvw；|uv|N；|v|1；即v串不能是空串。对于任意的整数i0，串uviwL(M)；N不大于接收语言L的最小的有限状态自动机的状态数。,定理4-6 右线性语言的泵浦引理的简单表述自动机M是有N个状态的有限状态自动机，若串wL(M)，且|z|N，则z能够记为uvw，且对所有的i0，串uviwL(M)。,实际

27、上，将串z划分为uvw的形式，可能有多种，因为接收串z的有限状态自动机的状态转换图可能会存在多个回路(循环)，那么，每个回路所接收的子串，都可以作为v串看待。,利用右线性语言的泵浦引理，可以证明某些语言不是右线性语言，即用反证法证明语言不满足泵浦引理。,例,证明0n1n|n1不是RL。证明：令L=0n1n|n1。假设L是RL，则它满足泵引理。不妨设N是泵引理中仅依赖于L的正整数，取 z=0N1N，显然 zL此时必然u,v,w st.z=uvw,|uv|N,|v|1，因此v只可能是由0组成的非空串设 v=0k，k 1;w=0j1N则 u=0N-k-j,从而有 uviw=0N-k-j(0k)i0j

28、1N 当i=2时，uv2w=0N-k-j 02k0j1N=0N+k1N由于k 1，N+kN 也就是说，uv2wL，这与泵引理矛盾。所以，L不是RL,例,证明0n|n为素数不是RL。简证：假设它为RL，且有一个长度为N+p(取这样的长度是为了保证其N)的串，则可以有长度为k的0串可以被随意地泵进，N+p+ik均保持为一个素数，显然，当 i=N+p 时 N+p+ik=(N+p)(k+1)为一个合数。矛盾。因此它不是RL。,例,证明0n 1m 2n+m|m,n 1不是RL。证明：令L=0n 1m 2n+m|m,n 1。假设L是RL，则它满足泵引理。不妨设N是泵引理中仅依赖于L的正整数，取 z=0N1N22N，显然 zL此时必然u,v,w st.z=uvw,|uv|N,|v|1，因此v只可能是由0组成的非空串设 v=0k，k 1;w=0j1N22N则 u=0N-k-j,从而有 uviw=0N-k-j(0k)i0j1N22N 当i=0时，uv0w=0N-k1N22N由于k 1，N-k+N 2N 也就是说，uv0wL，这与泵引理矛盾。所以，L不是RL,4.3 略。4.4 略。4.5 略。,