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

《有限自动机理论-4章正则语言.ppt》由会员分享，可在线阅读，更多相关《有限自动机理论-4章正则语言.ppt（134页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章第四章正则语言正则语言l正正则则表表达达式式RE与与有有限限状状态态自自动动机机DFA(或或NFA)是等价的。是等价的。l一一个个语语言言L，如如果果能能够够被被有有限限状状态态自自动动机机所所接接收收，则则一一定定存存在在着着对对应应的的正正则则表表达达式式来来代代表表该该语语言言(该该语语言言就是正则集就是正则集)；l一一个个语语言言L，如如果果能能够够被被正正则则表表达达式式来来表表示示，则则一一定定存存在在着着对对应应的的有有限限状状态态自自动动机机，能能够够接接收收该该语语言言(该该语语言言就是就是FSL)；l每个每个FSL都是都是正则集正则集。l右右线线性性语语言言，正正则则

2、集集和和FSL是是等等价价的的，只只不不过过是是从从不不同同的的角角度度来来对对语语言言进进行的描述：行的描述：l右线性右线性文法文法产生右线性语言；产生右线性语言；l通过通过运算运算得到正则集；得到正则集；l有限状态自动机有限状态自动机DFA(或或NFA)接收接收FSL。l正则正则表达式表达式表示正则语言。表示正则语言。4.1 正则语言与有限状态自动机正则语言与有限状态自动机l4.1.1正则表达式与有限状态自动机正则表达式与有限状态自动机l可可以以直直接接构构造造有有限限状状态态自自动动机机NFA接接收收正则表达式正则表达式表示的表示的正则语言正则语言。l例例4-1简简单单的的正正则则表表达

3、达式式和和对对应应的的有有限限状状态自动机的情况。态自动机的情况。P87l正则表达式正则表达式0对应的对应的NFA:l正则表达式正则表达式01对应的对应的NFA:l正则表达式正则表达式0+1对应的对应的NFA:ll或构造仅有一个接收状态的带或构造仅有一个接收状态的带-NFA:l正则表达式正则表达式0*对应的有限状态自动机对应的有限状态自动机:l对对于于比比较较复复杂杂的的正正则则表表达达式式，如如何何得得到所对应的到所对应的有限状态自动机有限状态自动机?定理定理4-1l设设r是是一一个个正正则则表表达达式式，则则存存在在一一个个带带动动 作作 的的 有有 限限 状状 态态 自自 动动 机机，有

4、有L(NFA)=S(r)。证明:l对对于于正正则则表表达达式式r中中三三种种运运算算(连连接接、联联合合和和迭迭代代)的的数数目目n作作归归纳证明纳证明:l对于正则表达式对于正则表达式r，存在一个等价的，存在一个等价的-NFA;l该该-NFA只只有有一一个个接接收收状状态态,且且没没有有从该接收状态出发的任何从该接收状态出发的任何状态转换状态转换。归纳基础：l设设正正则则表表达达式式r的的构构造造次次数数n为为0，即即r没没有有经经过过任任何何运运算算(连连接接、联联合合和和迭迭代代)而而得得，因因此此，r只只能能为为、或或者者是是字字母母表表中中的的某个元素某个元素a。l1)r=2)r=3)

5、r=al所以，结论对于所以，结论对于n=0成立；成立；归纳步骤：l假假设设结结论论对对nk(k0)成成立立，则则当当n=k+1，根根据据r最最后后一一次次运运算算的的形形式式，分分为为三三种种情情况：况：l1)r=r1+r2lr1和和r2中中所所含含的的运运算算符符的的个个数数不不会会大大于于k，根根据据归归纳纳假假设设，存存在在满满足足定定理理要求的要求的-NFA。lM1=(Q1，1，1，q1，f1)和和lM2=(Q2，2，2，q2，f2)l且且lL(M1)=S(r1)；L(M2)=S(r2)l假设假设Q1和和Q2不相交，不相交，l设置设置Q=Q1UQ2Uq0,f0,l=1U2l构造构造l-

6、NFA=(Q,q0，f0)其中函数为：l(q0，)=q1，q2l对于对于qQ1-f1，a1U，(q，a)=1(q，a)；l对于对于qQ2-f2，a2U，l(q，a)=2(q，a)；l(f1，)=f0(f2，)=f0l对于构造出的对于构造出的-NFA，可以形象地表示，可以形象地表示:l该该-NFA包包括括了了原原来来M1和和M2的的所所有有函函数数，增加了增加了4个个扫描扫描的的函数函数，使得：，使得：l从从-NFA的的开开始始状状态态出出发发，通通过过两两个个动动作作，可可以以选选择择地地到到达达M1或或M2的的开开始始状状态态q1或或q2，然然后后，使使用用M1或或M2的的自自己己的的函函数

7、数，到到达达M1或或M2的的惟惟一一接接收收状状态态f1或或f2，最最后后，进入进入NFA的惟一接收状态的惟一接收状态f0。l显显然然，-NFA接接收收的的语语言言是是L(M1)和和L(M2)的联合，即的联合，即r=r1+r2。l2)r=r1r2lr1和和r2中中所所含含的的运运算算符符的的个个数数不不会会大大于于k，根根据据归归纳纳假假设设，存存在在满满足足定定理理要要求求的的-NFA：llM1=(Q1，1，1，q1，f1)和和lM2=(Q2，2，2，q2，f2)l且且L(M1)=S(r1)，L(M2)=S(r2)l假设假设Q1和和Q2不相交，现构造不相交，现构造l-NFA=(Q1UQ2，1

8、U2,q1，f2)其中函数为l对于对于qQ1-f1，a1U(q，a)=1(q，a)；l(f1，)=q2l对于对于qQ2-f2，a2U，(q，a)=2(q，a)；l对于构造出的对于构造出的-NFA，可以形象地表示：，可以形象地表示：l该该-NFA包包括括了了原原来来M1和和M2的的所所有有函函数数，增加了增加了1个个扫描扫描的的函数函数，使得：，使得：l-NFA从从M1的的开开始始状状态态q1出出发发，使使用用M1自自己己的的函函数数，到到达达M1的的惟惟一一接接收收状状态态f1，使使用用新新增增加加的的函函数数(f1，)=q2，到到达达M2的的开开始始状状态态q2，然然后后，使使用用M2自自己

9、己的的函函数数，到到达达M2的的惟惟一一接接收收状状态态f2(也也是是构构造造的的-NFA的惟一接收状态的惟一接收状态)。l显显然然，-NFA接接收收的的语语言言是是L(M1)和和L(M2)的连接，即的连接，即r=r1r2。l3)r=r1*lr1中中所所含含的的运运算算符符的的个个数数不不会会大大于于k，根根据据归归纳纳假假设设，存存在在满满足足定定理理要要求求的的-NFA：llM1=(Q1，1，1，q1，f1)l使得：使得：L(M1)=S(r1)l设置设置Q=Q1Uq0,f0,l构造构造l-NFA=(Q，1，q0，f0)其中函数为：l(q0，)=q1，f0l对于对于qQ1-f1，a1U(q，

10、a)=1(q，a)；l(f1，)=q0，f0l对于构造出的对于构造出的-NFA，可以形象地表示：，可以形象地表示：l该该-NFA包包括括了了原原来来M1的的所所有有函函数数，增增加了加了4个扫描个扫描的的函数，使得：函数，使得：l从从-NFA的的开开始始状状态态出出发发，通通过过两两个个动动作作，可可以以直直接接进进入入NFA的的惟惟一一接接收收状状态态f0(以以便便能能够够接接收收空空串串)；或或者者到到达达M1的的开开始始状状态态q1，然然后后，从从M1的的开开始始状状态态q1出出发发，使使用用M1自自己己的的函函数数，到到达达M1的的惟惟一一接接收收状状态态f1，l通通过过两两个个动动作

11、作，可可以以直直接接进进入入-NFA的的接接收收状状态态f0，以以便便结结束束接接收收过过程程；也也可可以以再再将将状状态态转转换换为为M1的的开开始始状状态态q1，以以便便迭迭代代地接收输入串。地接收输入串。l显显然然，-NFA接接收收的的语语言言是是L(M1)的的闭闭包包，即即r=r1*。l根根据据r最最后后一一次次运运算算的的三三种种情情况况，可可知知，当当n=k+1，结论也成立。，结论也成立。l对对于于正正则则表表达达式式r，存存在在一一个个等等价价的的-NFA，l该该-NFA只只有有一一个个接接收收状状态态,且且没没有有从从该该接接收状态出发的任何收状态出发的任何状态转换状态转换。l

12、该该定定理理也也说说明明了了正正则则语语言言对对于于联联合合、连连接接和和闭包闭包三种运算是三种运算是封闭封闭的。的。例例4-2l为正则表达式为正则表达式10*+0构造等价的构造等价的NFA。l分析：分析：l根据运算符的优先级，正则表达式根据运算符的优先级，正则表达式10*+0实际上为：实际上为：l（1（0*）+0l是是r1+r2（联合）的形式；其中：（联合）的形式；其中：r1=10*，r2=0；lr1可以表示为可以表示为r3r4的形式；其中：的形式；其中：r3=1，r4=0*；l可以简化为无可以简化为无的的NFA定理4-2l如如果果语语言言L被被一一个个DFA所所接接收收，则则语语言言L可以

13、用一个可以用一个正则表达式正则表达式来表示。来表示。l证明：证明：l设设语语言言L被被DFA=(Q，q1，F)所接收；所接收；l状状态态集集合合Q中中有有n个个状状态态，按按任任意意顺顺序序进进行行编编号号；即即Q=q1，q2，q3，qn。l使使用用记记号号Rijk代代表表字字符符串串的的集集合合，具体定义为：具体定义为：lRijk=w|*(qi，w)=qj，且且对对于于w的的任任何何前前缀缀x(xw，x)，如如果果*(qi，x)=ql，则，则lklRijk是是所所有有那那些些将将DFA从从给给定定状状态态qi引引导导到到状状态态qj，并并且且中中间间不不经经过过（进进入入并并离离开开）编编号

14、号大大于于k的的任任何何状状态态的的所所有字符串的集合，有字符串的集合，l要要注注意意的的是是，i，j的的大大小小与与k的的大大小小无无关；关；l显显然然，Rijn是是所所有有那那些些将将DFA从从给给定定状态状态qi引导到状态引导到状态qj的字符串的集合。的字符串的集合。l根据定义，可以得出如下的递推公式：根据定义，可以得出如下的递推公式：la|(qi，a)=qj若若ijlRij0=la|(qi，a)=qjU若若i=jlRijk=Rikk-1(Rkkk-1)*Rkjk-1URijk-1l(k=1,2,3,n)l输输入入串串w使使DFA由由状状态态qi到到状状态态qj，且且中中间间不不经经过过

15、编编号号大大于于k的的任任何何状状态态，只可能有两种情况：只可能有两种情况：l(1)w在在Rijk-1中中，即即中中间间不不经经过过编编号号大大于等于于等于k（不超过（不超过k-1）的任何状态；）的任何状态；l(2)在在由由状状态态qi到到状状态态qj的的过过程程中中，中中间间可可能能经经过过一一个个或或者者多多个个qk状状态态，即即状态变化序列呈下述形式状态变化序列呈下述形式lqiqkqkqkqjl其其中中：在在处处出出现现的的状状态态的的编编号号均均小小于于k；l从从qiqk读读过过的的w的的子子串串属属于于Rikk-1，从从 qkqkqk读读 过过 的的 w的的 子子 串串 属属 于于(

16、Rkkk-1)*，从从qkqj读读过过的的w的的子子串串属属于于Rkjk-1。l现现在在证证明明，对对于于任任何何Rijk，存存在在正正则则表表达达式式rijk能能代代表表的的Rijk，可可采采用用对对k的的归纳法进行证明。归纳法进行证明。归纳基础：lk=0时，因为时，因为la|(qi，a)=qj若若ijlRij0=la|(qi，a)=qjU若若i=jl即即Rij0是是一一个个有有穷穷集集，其其中中每每个个元元素素，或是或是中的元素或是中的元素或是。lRij0=a1+a2+ap若若ij或或lRij0=a1+a2+ap+若若i=jl其其中中a1，a2，ap是是使使(qi，a)=qj的一切字母的一

17、切字母a的集合。的集合。归纳步骤：l假假设设对对lk的的l，Rijl，都都已已经经求求出出对对应应的的正正则则表表达达式式rijl代代表表Rijl，现现考考虑虑l=k，根据递推公式，存在正则表达式，根据递推公式，存在正则表达式lrijk=rikk-1(rkkk-1)*rkjk-1Urijk-1代表代表Rijk。l设设DFA的的接接收收状状态态集集合合F=qj1，qj2，qj3，qjp，因因为为q1是是开开始始状状态态，qj是是接接收收状状态态之之一一，R1jn表表示示状状态态q1到到状状态态qj且且中中间间不不经经过过编编号号大大于于n的的状状态态（因因为为n是是状状态态最最大大的的编编号号，

18、也也就就是是说说，对对于于中中间间经经过过的的状状态态不不加加任任何何限限制）所读过的字符串的集合，则制）所读过的字符串的集合，则l该该DFA接收的语言对应的正则表达式为：接收的语言对应的正则表达式为：lr1j1n+r1j2n+r1jpnl即即lL（DFA）=R1j1nUR1j2nUUR1jpnl=UR1fnqfFl所所以以，对对于于任任何何Rijk，存存在在正正则则表表达达式式rijk能代表的能代表的Rijk。证毕。证毕。l例例4-3对于给定的对于给定的DFA，给出对应的正，给出对应的正则表达式。则表达式。k=0 k=1 k=2lr11k(00)*lr12k000(00)*lr13k110*

19、1lr21k000(00)*lr22k+00(00)*lr23k11+010*1lr31k(0+1)(00)*0lr32k0+10+1(0+1)(00)*lr33k+(0+1)0*1l其中某些正则表达式已经被化简；其中某些正则表达式已经被化简；l例如例如lr221=r210(r110)*r120+r220=0()*0+,可可以以化简为化简为00+；l又例如又例如lr132=r121(r221)*r231+r131=0(+00)*(1+01)+1,由由于于(+00)*可可以以化化简简为为(00)*，(1+01)可可以以化简为化简为(+0)1，则，则lr132=0(00)*(+0)1+1l由于由于

20、(00)*(+0)可以化简为可以化简为0*,于是于是,lr132=00*1+1=0*1l由由于于L(DFA)=R123UR133,所所以以,代代表表该该语言的正则表达式为语言的正则表达式为r123+r133,则则lr123=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)*lr133=r132(r332)*r332+r132l=0*1(+(0+1)0*1)*(+(0+1)0*1)+0*1l=0*1(0+1)0*1)*(+(0+1)0*1)+0*1l=0*1(0+1)0*1)*D

21、+(0+1)0*1)*(0+1)0*1)+)l=0*1(0+1)0*1)*l因此因此lr123+r133=0*1(0+1)0*1)*(0+1)(00)*+0(00)*+0*1(0+1)0*1)*l=0*1(0+1)0*1)*(0+1)(00)*+)+0(00)*l使使用用上上述述方方法法求求一一个个DFA接接收收语语言言的的正正则则表表达达式式对对于于计计算算机机系系统统而而言言是是比比较较容容易易的的,而而如如果果需需要要“人人为为”地地来来进进行行，还还是是比比较较烦烦琐琐的的，下下面面介介绍绍一一种种“图图上上作作业业”的的方方法法，顾顾名名思思义义，这这种种方方法法是是通通过过对对DF

22、A的的状状态态转转换换图图的的处处理理来来直直接接获获取取等等价价的的正正则则表达式的方法。表达式的方法。l在在这这里里，放放宽宽对对DFA的的状状态态转转换换图图的的弧弧标标记记的的限限制制，允允许许弧弧上上的的标标记记可可以以直直接接是是字字母表上的正则表达式。母表上的正则表达式。l下面，给出一些基本的替换。下面，给出一些基本的替换。l由由于于DFA的的开开始始状状态态的的入入度度不不一一定定为为0(即即其其他他状状态态可可以以接接收收某某个个字字母母后后，DFA的的状状态态可可以以转转换换为为开开始始状状态态)，而而且且DFA的的接接收收状状态态也也可可能能不不止止一一个个，所所以以，需

23、需要要先先对对DFA的状态转换图进行适当的处理：的状态转换图进行适当的处理：l增增加加标标记记为为X和和Y的的两两个个状状态态：X状状态态为为新新的的开开始始状状态态，且且入入度度为为0；Y状状态态是是新新的的惟惟一一接接收收状状态态；然然后后，对对状状态态图图进进行行响响应应的的处处理理，直直到到整整个个图图最最后后只只剩剩下下X和和Y的的两两个状态，个状态，l以以及及从从X状状态态到到Y状状态态的的可可能能的的惟惟一一一一条条弧弧；而而这这条条弧弧上上标标记记的的正正则则表表达达式式，就就是是所所求求的的DFA所所接接收收语语言言对对应应的的正正则则表表达达式式。当当该该弧弧不不存存在在时

24、时，DFA所所接接收收语语言言为为，对应的正则表达式为对应的正则表达式为。l具具体体的的对对于于DFA=(Q，q0，F)的的状状态转换图进行处理的步骤为：态转换图进行处理的步骤为：(1)预处理l增加标记为增加标记为X和和Y的两个状态的两个状态l增增加加标标记记为为X和和Y的的两两个个状状态态，从从X状状态态到到原原来来的的开开始始状状态态q0引引入入一一条条弧弧，标标记记为为，使使得得X状状态态为为新新的的开开始始状状态态；从从每每一一个个接接收收状状态态引引一一条条弧弧到到Y状状态态，每每条条弧弧都都分分别别标标记记为为，使使得得Y状状态态为为新新的的惟惟一一接接收收状状态。态。(1)预处理

25、l去掉所有的不可到达状态。去掉所有的不可到达状态。l(2)对对已已经经经经过过预预处处理理的的DFA的的状状态态转转换换图图重重复复如如下下的的操操作作，直直到到该该图图中中仅仅仅仅只只剩剩下下X和和Y两两个个状状态态，并并且且这这两两个个状状态态之之间间最最多只有一条弧。多只有一条弧。l并弧并弧l对对图图中中任任意意两两个个状状态态q和和p，如如果果图图中中包包含含有有从从q到到p的的标标记记为为r1，r2，r3，rg的的并并行行的的弧弧，则则可可以以使使用用标标记记为为r1+r2+r3+rg的的弧弧取取代代这这g个个并并行行的的弧弧，其其中中，状状态态q和和p可可以以是是不不同同的的两两个

26、个状状态态，也也可可以以是是相相一一个状态。个状态。l去状态去状态1l对对图图中中任任意意三三个个状状态态q、p和和t，如如果果从从q到到p有有一一条条标标记记为为r1的的弧弧，从从p到到t有有一一条条标标记记为为r2的的弧弧，并并且且不不存存在在从从状状态态p出出发发的的其其他他的的弧弧，就就可可以以将将状状态态p去去掉掉，并并将将与与状状态态p相相关关联联的的两两条条弧弧去去掉掉，使使用用一一条条从从状状态态q到到t标记为标记为r1r2的弧来代替。的弧来代替。l去状态去状态2l对对图图中中任任意意三三个个状状态态q、p和和t，如如果果从从q到到p有有一一条条标标记记为为r1的的弧弧，从从p

27、到到t有有一一条条标标记记为为r2的的弧弧，并并且且存存在在从从状状态态p到到状状态态p本本身身标标记记为为r3的的弧弧，就就可可以以将将状状态态p去去掉掉，并并将将与与状状态态p相相关关联联的的三三条条弧弧都都去去掉掉，使使用用一一条从状态条从状态q到到t标记为标记为r1r3*r2的弧来代替。的弧来代替。l去状态去状态3l如如果果状状态态图图中中只只剩剩下下3个个状状态态，而而且且不不存存在在从从X状状态态到到Y状状态态的的路路，则则可可以以将将X状状态态和和Y状状态态之之外外的的第第3个个状状态态以以及及与与第第3个个状状态相关的所有弧都删除掉。态相关的所有弧都删除掉。l(3)X状状态态到

28、到Y状状态态的的弧弧上上所所标标记记的的正正则则表表达达式式就就是是原原来来DFA所所接接收收语语言言对对应应的的正正则则表表达达式式。如如果果从从X状状态态到到Y状状态态并并不不存存在在弧，则对应的正则表达式为弧，则对应的正则表达式为。l例例4-4求求DFA所接收语言对应的正则表达式。所接收语言对应的正则表达式。l执行步骤1（预处理），l去掉状态q3 l去掉状态q4 l合并从状态q2到状态Y的两条弧 l去掉状态q0 l合并状态q1的弧 l去掉状态q1 l去掉状态q2 l则得l1*0(11*0)*0(00*111*0+00*10+11*0)(11*0)*0)*（00*1+00*）l在在使使用用

29、“图图上上作作业业”方方法法时时，以以下下几几点点需需要注意：要注意：l如如果果删删除除状状态态的的顺顺序序不不一一致致，最最后后得得到到的的正正则则表表达达式式可可能能在在形形式式上上不不一一样样，但但它它们们都都是是等等价价的的；而而且且删删除除状状态态和和并并弧弧操操作作也也没没有有绝绝对对的的先先后后顺顺序序，一一般般地地，在在状状态态图图的的处处理理过过程程中中，优优先先地地执执行行并并弧弧操操作作，会会使使后后继继的的删删除除状状态态简简单单一一些些，因因为为增增加加的的弧会少一些。弧会少一些。l当当DFA的的接接收收状状态态都都是是不不可可到到达达状状态态时时，状状态态转转换换图

30、图中中肯肯定定不不存存在在从从开开始始状状态态到到某某个个接接收收状状态态的的路路；使使用用“图图上上作作业业”方方法法，最最终终会会去去掉掉除除状状态态X和和状状态态Y以以外外的的所所有有状状态态和和弧弧，这这种种情情况况下下，对对应应的的正正则则表表达达式为式为。l不不计计算算自自身身到到自自身身的的弧弧，如如果果状状态态q的的入入度度为为n，出出度度为为m，则则将将状状态态q及及相相关关的的弧弧去掉之后，需要增加去掉之后，需要增加n*m条新弧。条新弧。l对对于于操操作作步步骤骤进进行行归归纳纳假假设设，不不难难证证明明“图上作业图上作业”方法的正确性。方法的正确性。l按按照照“图图上上作

31、作业业”的的方方法法，最最后后，将将标标记记为为X和和Y的两个状态去掉，即得所需要的正则表达式。的两个状态去掉，即得所需要的正则表达式。l“图图上上作作业业”的的方方法法，也也可可以以当当作作一一个个算算法法，可可以以利利用用计计算算机机实实现现，有有兴兴趣趣的的读读者者可以进行试验。可以进行试验。4.1.2正则语言的等价模型正则语言的等价模型l正正则则语语言言有有5种种等等价价模模型型：正正则则文文法法(右右线线性性文文法法)RG，正正则则表表达达式式RE、确确定定的的有有限限状状态态自自动动机机DFA，不不确确定定的的有有限限状状态态自自动动机机NFA，带，带动作的有限状态自动机动作的有限

32、状态自动机-NFA。l正正则则语语言言的的5种种等等价价模模型型的的转转换换关关系系可可以以用图用图4-28表示。表示。5种等价模型之间的（直接）转换l1)DFA转换为转换为RGl2)RG转换为转换为NFAl3)NFA转换为转换为REl4)RE转换为转换为-NFAl5)-NFA转换为转换为NFAl6)NFA转换为转换为DFA4.2正则语言的泵浦引理正则语言的泵浦引理l任任何何有有穷穷语语言言都都是是正正则则语语言言，所所以以，任任何何非非正正则则语语言言都都肯肯定定是是无无穷穷语语言言。需需要要讨讨论的就是无穷语言是否为正则的语言。论的就是无穷语言是否为正则的语言。ll有有限限状状态态自自动动

33、机机时时识识别别正正则则语语言言的的模模型型。一一个个有有限限状状态态自自动动机机只只有有有有限限个个状状态态；这这就就是是说说，当当该该有有限限状状态态自自动动机机识识别别的的语语言言L是是有有穷穷语语言言时时，可可以以构构造造足足够够多多的的接接收收状状态态，每每个个接接收收状状态态对对应应识识别别语语言言L中中的的一一个个字字符符串串(如如果果状状态态q0，q1，q2，qm中中没没有有相相同同的的状状态态，则则m+1个个状状态态接接收收的的字符串仅有字符串仅有m个字符个字符)。l当当该该有有限限状状态态自自动动机机识识别别的的语语言言L是是无无穷穷语语言言时时，语语言言L必必定定存存在在

34、一一个个足足够够长长的的句句子子，使使得得有有限限状状态态自自动动机机在在识识别别该该句句子子的的过过程程中中，必必定定要要重重复复地地经经过过某某一一个个状状态态，即即在在该该有有限限状状态态自自动动机机的的状状态态转转换换图图中中存存在着回路在着回路(循环循环)。ll如如 果果 语语 言言 L的的 足足 够够 长长 的的 某某 个个 句句 子子 为为z=a1a2a3am，假假设设有有限限状状态态自自动动机机在在识识别别它它的的过过程程中中，需需要要经经过过的的状状态态依依次次为为q0，q1，q2，qm。Sa1q0q1qka2akak+1ajqjaj+1amqml根根据据鸽鸽笼笼原原理理,当

35、当m大大于于等等于于有有限限状状态态自自动动机机的的所所有有可可达达状状态态的的个个数数时时，这这些些状状态态中中至至少少有有一一对对是是重重复复出出现现的的，例例如如，qk和和qj是是 同同 一一 状状 态态；其其 中中：kj。如如 果果 v=ak+1ak+2aj是是引引导导有有限限状状态态自自动动机机从从状状态态qk到到状状态态qj的的子子串串，则则它它就就是是该该有有限限状状态态自自动动机机的的状状态态转转换换图图中中从从状状态态q0到到状状态态qm的的标标记记为为w的的路路中中从从状状态态qk到到状状态态qj的的标标记记为为v的的回回路路，因因此此，v在在它它出出现现的的位位置置无无论

36、论重重复复出出现现多多少少次次，所所构构成成的的字字符符串串都都一一定是该有限状态自动机所识别的句子。定是该有限状态自动机所识别的句子。l由由于于qk和和qj是是同同一一状状态态，为为方方便便理理解解，将将图改造。图改造。Sa1q0q1qk=qja2akak+1ajaj+1amqml根据鸽笼原理，这样的根据鸽笼原理，这样的qk和和qj状态在有限状态在有限状态自动机的状态序列状态自动机的状态序列q0，q1，qN中中是一定存在的，其中：是一定存在的，其中：N是有限状态自动是有限状态自动机所包含的状态的个数。机所包含的状态的个数。l此时有：此时有：l(q0,a1a2ak)=qk(q0,a1a2ak)

37、=qk，(qk,ak+1aj)=qj(qk,ak+1aj)=qj，(qj,aj+1am)=qm(qj,aj+1am)=qm，qmFqmFl对于任意整数对于任意整数i0i0，有：，有：l(q0,a1ak(ak+1aj)iaj+1am)=qm(q0,a1ak(ak+1aj)iaj+1am)=qm，即，即a1ak(ak+1aj)iaj+1am)L(M)a1ak(ak+1aj)iaj+1am)L(M)l取取u=a1a2aku=a1a2ak，v=ak+1ajv=ak+1aj，w=aj+1amw=aj+1am，那么有：，那么有：luviwLuviwL，|uv|N|uv|N，|v|1|v|1l下下面面给给出

38、出这这种种情情况况严严格格的的描描述述，并并给给出出判判定一个语言不是正则语言的一般方法。定一个语言不是正则语言的一般方法。l设设语语言言L是是一一个个正正则则的的语语言言，有有限限状状态态自自动机动机lM=(Q，q，F)l满足满足lL=L(M)l不不失失一一般般性性，设设状状态态集集合合Q中中不不含含任任何何不不可到达的状态，且可到达的状态，且|Q|=N。取语言。取语言L的句子的句子lz=a1a2a3am(mN)l对于整数对于整数h，1hm，令，令l*(q0，a1a2a3ah)=qhl由由于于mN，所所以以，在在状状态态序序列列q0，q1，qN中中至至少少有有两两个个状状态态是是相相同同的的

39、；假假设设这这两个状态为两个状态为qk和和qj，l即即lqk=qj；且；且kjN；l此时有此时有l*(q0，a1a2a3ak)=qkl*(qk，ak+1ak+2aj)=qj=qkl*(qj，aj+1aj+2am)=qml注意到注意到qj=qk，所有对于任意的整数，所有对于任意的整数i0，l*(qk,(ak+1ak+2aj)i)l=*(qk,(ak+1ak+2aj)i-1)l=*(qk,(ak+1ak+2aj)i-2)l=l=*(qk,ak+1ak+2aj)=qkl因为，因为，zL(M)l所以，所以，qmFl故，对于任意的整数故，对于任意的整数i0，l*(q0，a1a2ak(ak+1ak+2aj

40、)i-1ajaj+1am)=qml也就是说，也就是说，la1a2ak(ak+1ak+2aj)i-1ajaj+1amL(M)l取取lu=a1a2aklv=ak+1ak+2ajlw=ajaj+1aml于是，于是，luvwL(M)l对于任意的整数对于任意的整数i0，luviwL(M)l注注意意到到kN和和kN也就是说，也就是说，uv2w L，这与泵引理矛盾。，这与泵引理矛盾。所以，所以，L不是不是RL例例l证明证明0n|n为素数为素数不是不是RL。简证：假设它为简证：假设它为RL，且有一个长度为，且有一个长度为N+p(取这样的长度是为了保证其取这样的长度是为了保证其 N)的串，则的串，则可以有长度为

41、可以有长度为k的的0串可以被随意地泵进，串可以被随意地泵进，N+p+ik均保持为一个素数，显然，当均保持为一个素数，显然，当 i=N+p 时时 N+p+ik=(N+p)(k+1)为一个合数。矛盾。因此它不是为一个合数。矛盾。因此它不是RL。例例l证明证明0n 1m 2n+m|m,n 1不是不是RL。证明：令证明：令L=0n 1m 2n+m|m,n 1。假设。假设L是是RL，则它满足泵引理。不妨设，则它满足泵引理。不妨设N是泵引理是泵引理中仅依赖于中仅依赖于L的正整数，取的正整数，取 z=0N1N22N，显然，显然z L此时必然此时必然 u,v,wst.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+N2N也就是说，也就是说，uv0w L，这与泵引理矛盾。，这与泵引理矛盾。所以，所以，L不是不是RLl4.3略。略。l4.4略。略。l4.5略。略。