有限自动机理论-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不相交， 设

4、置Q= Q1UQ2Uq0,f0, =1U2 构造 -NFA=(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。,显然，-NF

5、A接收的语言是L(M1)和L(M2)的联合，即r=r1+r2。,2)r=r1r2 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的所有函数，

6、增加了1个扫描的函数，使得：,-NFA从M1的开始状态q1出发，使用M1自己的函数，到达M1的惟一接收状态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，)=

7、 q1，f0 对于qQ1-f1，a1U (q，a)=1(q，a)； (f1，)= q0，f0,对于构造出的-NFA ，可以形象地表示：,该-NFA包括了原来M1的所有函数，增加了4个扫描的函数，使得：,从-NFA的开始状态出发，通过两个动作，可以直接进入NFA的惟一接收状态f0(以便能够接收空串)；或者到达M1的开始状态q1，然后，从M1的开始状态q1出发，使用M1自己的函数，到达M1的惟一接收状态f1，,通过两个动作，可以直接进入-NFA的接收状态f0，以便结束接收过程；也可以再将状态转换为M1的开始状态q1，以便迭代地接收输入串。,显然，-NFA接收的语言是L(M1)的闭包，即r=r1*。

8、,根据r最后一次运算的三种情况，可知，当n=k+1，结论也成立。,对于正则表达式r，存在一个等价的-NFA， 该-NFA只有一个接收状态,且没有从该接收状态出发的任何状态转换。,该定理也说明了正则语言对于联合、连接和闭包三种运算是封闭的。,例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可以用一个正则表达式来表示。 证明：

9、设语言L被DFA=(Q，q1，F)所接收；,状态集合Q中有n个状态，按任意顺序进行编号；即Q=q1，q2，q3，qn。 使用记号Rijk代表字符串的集合，具体定义为：,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 若ij Ri

10、j0= a|(qi，a)= qjU 若i=j,Rijk= Rikk-1(Rkkk-1)*Rkjk-1URijk-1 (k=1,2,3,n),输入串w使DFA由状态qi到状态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的子串属于R

11、kjk-1。 现在证明，对于任何Rijk，存在正则表达式rijk能代表的Rijk，可采用对k的归纳法进行证明。,归纳基础：,k=0时，因为 a|(qi，a)= qj 若ij Rij0= a|(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)*

12、 rkjk-1Urijk-1代表Rijk。,设DFA的接收状态集合F=qj1，qj2，qj3，qjp，因为q1是开始状态，qj是接收状态之一，R1jn表示状态q1到状态qj且中间不经过编号大于n的状态（因为n是状态最大的编号，也就是说，对于中间经过的状态不加任何限制）所读过的字符串的集合，则,该DFA接收的语言对应的正则表达式为： r1j1n+r1j2n+r1jpn 即 L（DFA）= R1j1nUR1j2nUUR1jpn =UR1fn qfF 所以，对于任何Rijk，存在正则表达式rijk能代表的Rijk。证毕。,例4-3对于给定的DFA，给出对应的正则表达式。,k=0 k=1 k=2,r1

13、1k (00)* r12k 0 0 0(00)* r13k 1 1 0*1 r21k 0 0 0(00)* r22k + 00 (00)* r23k 1 1 + 01 0*1 r31k (0+1)(00)*0 r32k 0+1 0+1 (0+1)(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(0

14、0)*(+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*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)

15、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接收语言的正则表达式对于计算机系统而言是比较容易的,而如果需要“人为”地来进行，还是比较烦琐的，下面介绍一种“图上作业”的方法，顾名思义，这种方法是通过对DFA的状态转换图的处理来直接获取等价的正则表达式的方法。,在这里，放宽对DFA的状态转换图的弧标记的限制，允许弧上的标记可以直接是字母表上的正则表达式。 下面，给出一些基

16、本的替换。,由于DFA的开始状态的入度不一定为0(即其他状态可以接收某个字母后，DFA的状态可以转换为开始状态)，而且DFA的接收状态也可能不止一个，所以，需要先对DFA的状态转换图进行适当的处理：,增加标记为X和Y的两个状态：X状态为新的开始状态，且入度为0；Y状态是新的惟一接收状态；然后，对状态图进行响应的处理，直到整个图最后只剩下X和Y的两个状态，,以及从X状态到Y状态的可能的惟一一条弧；而这条弧上标记的正则表达式，就是所求的DFA所接收语言对应的正则表达式。当该弧不存在时，DFA所接收语言为，对应的正则表达式为。,具体的对于DFA=(Q，q0，F)的状态转换图进行处理的步骤为：,(1)

17、预处理,增加标记为X和Y的两个状态 增加标记为X和Y的两个状态，从X状态到原来的开始状态q0引入一条弧，标记为，使得X状态为新的开始状态；从每一个接收状态引一条弧到Y状态，每条弧都分别标记为，使得Y状态为新的惟一接收状态。,(1)预处理,去掉所有的不可到达状态。,(2)对已经经过预处理的DFA的状态转换图重复如下的操作，直到该图中仅仅只剩下X和Y两个状态，并且这两个状态之间最多只有一条弧。,并弧 对图中任意两个状态q和p，如果图中包含有从q到p的标记为r1，r2，r3，rg的并行的弧，则可以使用标记为r1+r2+r3+rg的弧取代这g个并行的弧，其中，状态q和p可以是不同的两个状态，也可以是相

18、一个状态。,去状态1 对图中任意三个状态q、p和t，如果从q到p有一条标记为r1的弧，从p到t有一条标记为r2的弧，并且不存在从状态p出发的其他的弧，就可以将状态p去掉，并将与状态p相关联的两条弧去掉，使用一条从状态q到t标记为r1r2的弧来代替。,去状态2 对图中任意三个状态q、p和t，如果从q到p有一条标记为r1的弧，从p到t有一条标记为r2的弧，并且存在从状态p到状态p本身标记为r3的弧，就可以将状态p去掉，并将与状态p相关联的三条弧都去掉，使用一条从状态q到t标记为r1r3*r2的弧来代替。,去状态3 如果状态图中只剩下3个状态，而且不存在从X状态到Y状态的路，则可以将X状态和Y状态之

19、外的第3个状态以及与第3个状态相关的所有弧都删除掉。,(3)X状态到Y状态的弧上所标记的正则表达式就是原来DFA所接收语言对应的正则表达式。如果从X状态到Y状态并不存在弧，则对应的正则表达式为。,例4-4 求DFA所接收语言对应的正则表达式。,执行步骤1（预处理），,去掉状态q3,去掉状态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*）,在使用“图上作业”方法时，以下几点需要注意：,如果删除状态的顺序不一致，最后得到的正则表达式可能在形

20、式上不一样，但它们都是等价的；而且删除状态和并弧操作也没有绝对的先后顺序，一般地，在状态图的处理过程中，优先地执行并弧操作，会使后继的删除状态简单一些，因为增加的弧会少一些。,当DFA的接收状态都是不可到达状态时，状态转换图中肯定不存在从开始状态到某个接收状态的路；使用“图上作业”方法，最终会去掉除状态X和状态Y以外的所有状态和弧，这种情况下，对应的正则表达式为。,不计算自身到自身的弧，如果状态q的入度为n，出度为m，则将状态q及相关的弧去掉之后，需要增加n*m条新弧。 对于操作步骤进行归纳假设，不难证明“图上作业”方法的正确性。 按照“图上作业”的方法，最后，将标记为X和Y的两个状态去掉，即

21、得所需要的正则表达式。,“图上作业”的方法，也可以当作一个算法，可以利用计算机实现，有兴趣的读者可以进行试验。,4.1.2 正则语言的等价模型,正则语言有5种等价模型：正则文法(右线性文法)RG，正则表达式RE、确定的有限状态自动机DFA，不确定的有限状态自动机NFA，带动作的有限状态自动机-NFA。 正则语言的5种等价模型的转换关系可以用图4-28表示。,5种等价模型之间的（直接）转换,1) DFA 转换为RG 2) RG转换为NFA 3) NFA转换为RE 4) RE转换为-NFA 5) -NFA转换为NFA 6) NFA转换为DFA,4.2 正则语言的泵浦引理,任何有穷语言都是正则语言，

22、所以，任何非正则语言都肯定是无穷语言。需要讨论的就是无穷语言是否为正则的语言。,有限状态自动机时识别正则语言的模型。一个有限状态自动机只有有限个状态；这就是说，当该有限状态自动机识别的语言L是有穷语言时，可以构造足够多的接收状态，每个接收状态对应识别语言L中的一个字符串(如果状态q0，q1，q2，qm中没有相同的状态，则m+1个状态接收的字符串仅有m个字符)。,当该有限状态自动机识别的语言L是无穷语言时，语言L必定存在一个足够长的句子，使得有限状态自动机在识别该句子的过程中，必定要重复地经过某一个状态，即在该有限状态自动机的状态转换图中存在着回路(循环)。,如果语言L的足够长的某个句子为z=a

23、1a2a3am，假设有限状态自动机在识别它的过程中，需要经过的状态依次为q0，q1，q2，qm。,根据鸽笼原理,当m大于等于有限状态自动机的所有可达状态的个数时，这些状态中至少有一对是重复出现的， 例如，qk和qj是同一状态；其中：kj。如果v= ak+1ak+2aj 是引导有限状态自动机从状态qk到状态qj的子串，则它就是该有限状态自动机的状态转换图中从状态q0到状态qm的标记为w的路中从状态qk到状态qj的标记为v的回路，因此，v在它出现的位置无论重复出现多少次，所构成的字符串都一定是该有限状态自动机所识别的句子。,由于qk和qj是同一状态，为方便理解，将图改造。,根据鸽笼原理，这样的qk

24、和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)iaj+1am)L(M) 取u=a1a2ak，v=ak+1aj，w=aj+1am，那么有： uviwL，|uv|N，|v|1,下面给出这种情况严格的描述，并给出判定一个语言不是正则语言的一般方法。 设语言L是一个正则的语言，有限状态自动机 M=(Q，q，F) 满足 L=L

25、(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，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

26、)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， uviwL(M),注意到kN和kj，所以，u和v满足下面的条件： |uv|N 且 |v|1。 根据讨论的有限状态自动机的任意性，得到下面的引理。,引理4-5 正则语言的泵浦引理,设语言L为一个正则语言，则

27、存在仅依赖与语言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)。,实际上，将串z划分为uvw的形式，可能有多种，因为接收串z的有限状态自动机的状态转换图可能会存在多个回路(循环)，那么，每个回路所接收的子串，都可以作为v串看待。,利用右线性语言的泵浦引理，

28、可以证明某些语言不是右线性语言，即用反证法证明语言不满足泵浦引理。,例,证明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)i0j1N 当i = 2时， uv2w = 0N-k-j 02k0j1N = 0N+k1N 由于k 1 ，N+kN 也就是说， u

29、v2wL，这与泵引理矛盾。 所以， 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 略。,