《形式语言与自动机》课件ch3.7-3.8.ppt

1、12023-5-22School of Computer Science,BUPT3.7 正则表达式与有限自动机的关系结论结论:有限自动机、右（左）线性文法、正则表有限自动机、右（左）线性文法、正则表达式都定义了同一种语言达式都定义了同一种语言-正则语言正则语言.证明策略证明策略 -NFANFADFARERE(Regular Expression)-正则表达式22023-5-22School of Computer Science,BUPT从从 DFA 构造等价的构造等价的正则表达式正则表达式（状态消去法）（状态消去法）思路思路:(1)扩展自动机的概念，允许正则表达式作为转移弧的标记。这样，就

2、有可能在消去某一中间状态时，保证自动机能够接受的字符串集合保持不变。(2)在消去某一中间状态时，与其相关的转移弧也将同时消去，所造成的影响将通过修改从每一个前趋状态到每一个后继状态的转移弧标记来弥补。以下分别介绍中间状态的消去与正则表达式构造过程。32023-5-22School of Computer Science,BUPT从从 DFA 构造等价的构造等价的正则表达式正则表达式（中间状态的消去）（中间状态的消去）xy r1r2xz r1y r2代之以：xy r1+r2xyr2r1代之以：xy r1*xz y r1代之以：42023-5-22School of Computer Scienc

3、e,BUPT从从 DFA 构造等价的构造等价的正则表达式正则表达式（中间状态的消去）（中间状态的消去）sSq1qkp1pmP1PmQkQ1R11R1mRkmRk1R11+Q1S*P1R1m+Q1S*PmRkm+QkS*PmRk1+QkS*P1q1p1qkpm消去消去 s52023-5-22School of Computer Science,BUPT从从 DFA 构造等价的构造等价的正则表达式正则表达式（状态消去法）（状态消去法）步骤步骤:(1)对每一终态对每一终态q，依次消去除依次消去除 q 和初态和初态 q0 之外的其它状态之外的其它状态;StartRStartSTUR(2)若若q q0，

4、最终可得到一般最终可得到一般形式如下左图形式如下左图的状态自动机，的状态自动机，该自动机对应的正则表达式可表示为该自动机对应的正则表达式可表示为 (R+SU*T)*SU*.(3)若若q=q0，最终可得到最终可得到如下右图的自动机，它对应的正则如下右图的自动机，它对应的正则 表达式可以表示为表达式可以表示为 R*.(4)最终最终的正则表达式为的正则表达式为每一终态对应的每一终态对应的 正则表达式之和（并）正则表达式之和（并）.62023-5-22School of Computer Science,BUPT状态消去法举例状态消去法举例A0+1StartBCD10+10+1对于终态对于终态CA0+

5、1StartC1(0+1)A0+1StartD1(0+1)(0+1)对于终态对于终态D等价的正则表达式等价的正则表达式(0+1)*1(0+1)+(0+1)*1(0+1)(0+1)72023-5-22School of Computer Science,BUPT状态消去法举例状态消去法举例01342567 a b aa b b a b012567a+ba+b aabb0257(a+b)*(a+b)*aa+bb07(a+b)*(aa+bb)(a+b)*82023-5-22School of Computer Science,BUPT定理定理:L 是正则表达式是正则表达式 R 表示的语言表示的语言,

6、则存在一个则存在一个 -NFA E,满足满足 L(E)=L(R)=L.证明证明:构造性证明构造性证明.可以通过结构归纳法证明从可以通过结构归纳法证明从 R 可以构可以构造出与其等价的，满足如下条件的造出与其等价的，满足如下条件的 -NFA：(1)恰好一个终态恰好一个终态;(2)没有弧进入初态；没有弧进入初态；(3)没有弧离开终态；没有弧离开终态；从从正则表达式正则表达式构造等价的构造等价的 -NFA92023-5-22School of Computer Science,BUPT基础基础:从从正则表达式正则表达式构造等价的构造等价的 -NFA（归纳归纳构造过程）构造过程）1 对于对于 ，构造为

7、构造为 3 对于对于 a，构造为构造为a2 对于对于 ，构造为构造为102023-5-22School of Computer Science,BUPT归纳归纳:从从正则表达式正则表达式构造等价的构造等价的 -NFA（归纳归纳构造过程）构造过程）1 对于对于 R+S，构造为构造为SR 112023-5-22School of Computer Science,BUPT归纳归纳:从从正则表达式正则表达式构造等价的构造等价的 -NFA（归纳归纳构造过程）构造过程）2 对于对于 RS，构造为构造为RS R3 对于对于 R*，构造为构造为 122023-5-22School of Computer S

8、cience,BUPT举例举例:设设正则表达式正则表达式 1*0(0+1)*,构造等价的构造等价的 -NFA.从从正则表达式正则表达式构造等价的构造等价的 -NFA100+1 11*132023-5-22School of Computer Science,BUPT从从正则表达式正则表达式构造等价的构造等价的 -NFA(0+1)*10 11001*0(0+1)*142023-5-22School of Computer Science,BUPT3.8 右线性语言与右线性语言与有限自动机有限自动机 至此，我们已学到正则集有三种定义方式，且这三种方式等价：1.正则集是含有，a 以及在并、连接和*运

9、算下封闭的语言2.由正规表达式定义的集合是正则集。3.由右线性文法生成的语言是正则集。此外，还有第四种方式：将正则集作为由有限自动机定义的集合。即 正则集(右线性语言)有限自动机152023-5-22School of Computer Science,BUPT右线性文法右线性文法 有限自动机有限自动机定理定理3.8.1：由任意右线性文法G定义的语言必然能被一个NFA M所接受。即L（G）L（M）证明思路（构造证明）证明思路（构造证明）：设右线性文法G（N，T，P，S），构造一个与G等价的有限自动机NFA M（Q，T，q0，F），其中：QN U H，H为一个新增加的状态,HN，q0S H，S

10、当S-属于P。H 否则 的定义为：的定义为：当当A a B P，则则 B （A，a）当当A a P,则则 H （A，a）对于任意输入，（H，a）。F=162023-5-22School of Computer Science,BUPT右线性文法右线性文法 有限自动机有限自动机（例）例：例：设有右线性文法设有右线性文法G=(S,B,a,b,P,S)，其中其中P：SaB BaB|bS|a 试构造与试构造与G等价的有限自动机等价的有限自动机M。解：解：设设NFA M=(Q,T,q0,F)Q=S,B,H T=a,b q0=S F=H转换函数转换函数：n对于产生式对于产生式SaB，有有(S,a)=Bn对

11、于产生式对于产生式BaB，有有(B,a)=Bn对于产生式对于产生式BbS，有有(B,b)=Sn对于产生式对于产生式Ba，有有(B,a)=HSBH开始aaab172023-5-22School of Computer Science,BUPT右线性文法右线性文法 有限自动机有限自动机（续）（续）求证求证 G与与NFA M两者定义了同一语言。两者定义了同一语言。证明：证明：先证（先证（1）文法）文法G产生的语言产生的语言 L(G)能够被能够被NFA M所接收；所接收；再证（再证（2）NFA M 接受的语言接受的语言 L(M)可由文法可由文法G 产生。产生。182023-5-22School of

12、Computer Science,BUPT右线性文法右线性文法 有限自动机有限自动机（续）（续）证明方法：证明方法：通过两者定义的语言中任意一个字符串来说明。（1）设 =a1a2anL(G)，且n 1则有 S a1A1 a1a2A2 a1a2an-1An-1 a1a2 an-1a n则由的定义，有A1(S，a1)，A2(A1，a2),An-1(An-2，an-1)，H(An-1，an)，且 H(S，)因为H F,所以被NFA M 所接受。又若L（G）,则表明 S P,由 NFA M 的定义，有S F,即也被NFA M接受。所以，由文法所以，由文法G派生的任意字符串派生的任意字符串 L（M）。#

13、192023-5-22School of Computer Science,BUPT右线性文法右线性文法 有限自动机有限自动机（续）（续）（2）再证再证 L(M)可由可由G产生产生设=a1a2an 被NFA M接受，即 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 a n于是存在推导S a1A1 a1a2A2 a1a2an-1An-1 a1a2 an-1a n即a1a2an 是文法G的一个句子。也即也即 L（G）。）

14、。#202023-5-22School of Computer Science,BUPT有限自动机有限自动机 右线性文法右线性文法定理定理3.8.2：设有限自动机设有限自动机 M 接受的语言为接受的语言为L(M)则存在右线性文法则存在右线性文法G，它产生的语言它产生的语言L(G)L(M)。证明思路：证明思路：构造一个右线性文法构造一个右线性文法G，使它接受由使它接受由NFA M定义的语言。定义的语言。构造方法：构造方法：设设 M（Q，T，q0，F），），构造一个右线性文法构造一个右线性文法G（N，T，P，S），），其中其中NQ，Sq0P定义为：定义为：若若（A，a）B 且且 B F，则则A a

15、B 在在P中中 若若（A，a）B 且且 B F，则则A a 和和A aB 在在P中中 L（M）L（G）的证明见书的证明见书 P65 （自学）。自学）。212023-5-22School of Computer Science,BUPT有限自动机有限自动机右线性文法右线性文法（例）例：例：设有设有DFA M=(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|b