《形式语言与自动机.ppt》由会员分享，可在线阅读，更多相关《形式语言与自动机.ppt（38页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、12022/12/25College of Computer Science&Technology,BUPT3.7 正则表达式与有限自动机的关系结结论论:有有限限自自动动机机、右右（左左）线线性性文文法法、正正则则表表达式都定义了同一种语言达式都定义了同一种语言-正则语言正则语言.证明策略证明策略 -NFANFADFARERE(Regular Expression)-正则表达式22022/12/25College of Computer Science&Technology,BUPT从从DFA 构造等价的构造等价的正则表达式正则表达式（状态消去法）（状态消去法）思路思路:(1)扩展自动机的概念
2、，允许正则表达式作为转移弧的标记.这样，就有可能在消去某一中间状态时，保证自动机能够接受的字符串集合保持不变.(2)在消去某一中间状态时，与其相关的转移弧也将同时消去，所造成的影响将通过修改从每一个前趋状态到每一个后继状态的转移弧标记来弥补.以下分别介绍中间状态的消去与正则表达式构造过程.32022/12/25College of Computer Science&Technology,BUPT从从DFA 构造等价的构造等价的正则表达式正则表达式（中间状态的消去）（中间状态的消去）xy r1r2xz r1y r2代之以：xy r1+r2xyr2r1代之以：xy r1*xz y r1代之以：42
3、022/12/25College of Computer Science&Technology,BUPT从从DFA 构造等价的构造等价的正则表达式正则表达式（中间状态的消去）（中间状态的消去）q1qkp1pmP1PmQkQ1R11R1mRkmRk1R11+Q1S*P1R1m+Q1S*PmRkm+QkS*PmRk1+QkS*P1q1p1qkpm消去消去s52022/12/25College of Computer Science&Technology,BUPT从从DFA 构造等价的构造等价的正则表达式正则表达式（状态消去法）（状态消去法）步骤步骤:(1)对每一终态对每一终态q，依次消去除依次消去
4、除q 和初态和初态q0 之外的其它状态之外的其它状态;(2)若若q q0，最终可得到一般最终可得到一般形式如下左图形式如下左图的状态自动机，的状态自动机，该自动机对应的正则表达式可表示为该自动机对应的正则表达式可表示为 (R+SU*T)*SU*.(3)若若q=q0，最终可得到最终可得到如下右图的自动机，它对应的正则如下右图的自动机，它对应的正则 表达式可以表示为表达式可以表示为 R*.(4)最终最终的正则表达式为的正则表达式为每一终态对应的每一终态对应的正则表达式之和（并）正则表达式之和（并）.62022/12/25College of Computer Science&Technology,
5、BUPT状态消去法举例状态消去法举例对于终态对于终态C对于终态对于终态D等价的正则表达式等价的正则表达式(0+1)*1(0+1)+(0+1)*1(0+1)(0+1)72022/12/25College 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)*82022/12/25College of Computer Science&Technology,BUPT定定理理:L 是是正正则则表
6、表达达式式R 表表示示的的语语言言,则则存存在在一一个个 -NFA E,满足满足L(E)=L(R)=L.证证明明:构构造造性性证证明明.可可以以通通过过结结构构归归纳纳法法证证明明从从R 可可以以构造出与其等价的，满足如下条件的构造出与其等价的，满足如下条件的 -NFA：(1)恰好一个终态恰好一个终态;(2)没有弧进入初态；没有弧进入初态；(3)没有弧离开终态；没有弧离开终态；从从正则表达式正则表达式构造等价的构造等价的 -NFA92022/12/25College of Computer Science&Technology,BUPT基础基础:从从正则表达式正则表达式构造等价的构造等价的 -
7、NFA（归纳归纳构造过程）构造过程）1 对于对于 ，构造为构造为 3 对于对于a，构造为构造为a2 对于对于 ，构造为构造为102022/12/25College of Computer Science&Technology,BUPT归纳归纳:从从正则表达式正则表达式构造等价的构造等价的 -NFA（归纳归纳构造过程）构造过程）1 对于对于R+S，构造为构造为 112022/12/25College of Computer Science&Technology,BUPT归纳归纳:从从正则表达式正则表达式构造等价的构造等价的 -NFA（归纳归纳构造过程）构造过程）2 对于对于RS，构造为构造为 3
8、 对于对于R*，构造为构造为 122022/12/25College of Computer Science&Technology,BUPT举例举例:设设正则表达式正则表达式1*0(0+1)*,构造等价的构造等价的 -NFA.从从正则表达式正则表达式构造等价的构造等价的 -NFA0+1 1*132022/12/25College of Computer Science&Technology,BUPT从从正则表达式正则表达式构造等价的构造等价的 -NFA(0+1)*1*0(0+1)*142022/12/25College of Computer Science&Technology,BUPT3.
9、8右线性语言与右线性语言与有限自动机有限自动机 至此，我们已学到正则集有三种定义方式，且这三种方式等价：1.正则集是含有，a以及在并、连接和*运算下封闭的语言2.由正规表达式定义的集合是正则集。3.由右线性文法生成的语言是正则集。此外，还有第四种方式：将正则集作为由有限自动机定义的集合。即正则集(右线性语言)有限自动机152022/12/25College of Computer Science&Technology,BUPT右线性文法右线性文法有限自动机有限自动机定定理理3.8.1：由任意右线性文法G定义的语言必然能被一个NFAM所接受。即L（G）L（M）证明思路（构造证明）证明思路（构造证
10、明）：设右线性文法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=162022/12/25College of Computer Science&Technology,BUPT右线性文法右线性文法有限自动机有限自动机（例）例：例：设有右线性文法设有右线性文法G=(S,B,a,b,P,S)，其中其中P：SaBBaB|bS|a试构造与试构造与G等价的有限自动机等价的有限自动机M。解
11、：解：设设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开始aaab172022/12/25College of Computer Science&Technology,BUPT右线性文法右线性文法有限自动机有限自动机（续）（续）求证求证G与与NFAM两者定义了同一语言。两者定义了同一语言。证明：证明：先证（先证（1）文法）文法G产生的语言产生的语言L(G)能够
12、被能够被NFAM所接收；所接收；再证（再证（2）NFAM接受的语言接受的语言L(M)可由文法可由文法G产生。产生。182022/12/25College 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所接受。又
13、若L（G）,则表明SP,由NFAM的定义，有SF,即也被NFAM接受。所以，由文法所以，由文法G派生的任意字符串派生的任意字符串 L（M）。#192022/12/25College 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
14、 an于是存在推导Sa1A1a1a2A2a1a2an-1An-1a1a2an-1an即a1a2an是文法G的一个句子。也即也即 L（G）。）。#202022/12/25College of Computer Science&Technology,BUPT课堂练习：课堂练习：练习：练习：设线性文法设线性文法G（S，A，B，a，b，P，S）P：SaA|baB|aAaA|aS|bBBbB|b|a构造相应的构造相应的NFAM。212022/12/25College of Computer Science&Technology,BUPT有限自动机有限自动机右线性文法右线性文法定理定理3.8.2：设有限自
15、动机设有限自动机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（自学）。自学）。222022
16、/12/25College 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,
17、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|b232022/12/25College of Computer Science&Technology,BUPT3.9右线性语言的性质右线性语言的性质主要内容：主要内容：DFA的极小化泵浦引理右线性语言的封闭性242022/12/25Co
18、llege 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可区分.252022/12/25College of Computer Science&Technology,BUPT确定有限自动机确定有限自动机DFA的化简的化简2不可达状态如果不存在任何T*，
19、使(q，)*(q，)，则称状态qQ为不可达状态.3最小化若DFA不存在互为等价状态及不可达状态，则称DFA是最小化的.262022/12/25College of Computer Science&Technology,BUPT最小化算法最小化算法一个DFA的最小化，是把的状态集构成一个划分。即:任何两个子集的状态都是可区分的；同一子集中的任何两个状态都是等价的。之后，每个子集用一个状态代表，并取一个状态名.构成划分的步骤构成划分的步骤:1.构成基本划分=，”，(为终态集，”为非终态集)2.细分=1，2，n，ii=q，q，q当输入任意字符a时，若i中的状态经标a的边可到达的状态集的元素分属于两
20、个不同的子集中，则将i细分为两个子集.重复步骤(2)，直至不可再细分，得到1.若1中有不可达状态，将其删除，1便是最小化的.272022/12/25College 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同一子
21、集对b，(q,b)=q，(q,b)=q，(q,b)=qq，q，q同一子集.将再分解.=q，q1，q3，q1，q3不可再细分，用q1表示q，q，q282022/12/25College of Computer Science&Technology,BUPT计算状态集划分的算法计算状态集划分的算法填表法填表法填表算法（填表算法（table-filling algorithm）基于如下递归地基于如下递归地标记可区别的状态偶对的过程标记可区别的状态偶对的过程:-基础基础如果如果p 为终态，而为终态，而q 为非终态，则为非终态，则p 和和q 标记标记为可区别的；为可区别的；-归纳归纳设设p 和和q 已标
22、记为可区别的已标记为可区别的,如果状态如果状态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)）292022/12/25College of Computer Science&Technology,BUPT计算状态集划分的算法计算状态集划分的算法填表法填表法填表算法举例填表算法举例xxxxxxxxxx
23、xxx(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,7302022/12/25College of Computer Science&Technology,BUPT通过合并等价的状态进行通过合并等价的状态进行DFA 的优化的优化步骤步骤1.删除所有从开始状态不可到达的状态及与其相关的边删除所有从开始状态不可到达的状态及与其相关的边,设所得到的设所得到的DFA为为A=(Q,T,q0,F)；2.使用填表算法找出所有等价的
24、状态偶对；使用填表算法找出所有等价的状态偶对；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)312022/12/25College of Computer Science&Technology,BUPT通过合并等价的状态进行通过合并等
25、价的状态进行DFA 的优化的优化举例举例划分结果：划分结果：1,2,3,4,5,6,7 等价的状态偶对为：等价的状态偶对为：（1,2）,（6,7）新的状态集合：新的状态集合：1,3,4,5,6322022/12/25College of Computer Science&Technology,BUPT最小化的最小化的DFA课堂练习课堂练习最小化下列最小化下列DFA:参考结果参考结果332022/12/25College of Computer Science&Technology,BUPT针对正则语言的针对正则语言的Pumping 引理引理正则语言应满足的一个必要条件用于判定给定的语言不是正则
26、集。物物理理意意义义：当给定一个正则集和该集合上一个足够长的字符串时，在该字符串中能找到一个非空的子串，并使子串重复，从而组成新的字符串。该新串必在同一个正则集内。定理：定理：设L是正则集，存在常数k，对字符串且，则可写成10，其中10，0，对所有的0有10i2。证明证明 设设L 是是DFA D=(Q,T,q0,F)的语言，的语言，取取k=|Q|即可即可.342022/12/25College of Computer Science&Technology,BUPTDFA的的“Pumping”特性特性设DFA D=(Q,T,q0,F),|Q|=n.对于任一长度不小于n 的字符串w=a1a2am,
27、其中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”特性：任一长度不小于状态数目 的字符串所标记的路径上，必然出现重复的状态.352022/12/25College of Computer Science&Technology,BUPTDFA的的“Pumping”特性特性“pumping”特性：特性：如前如前,设设DFA D
28、=(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+2am362022/12/25College of Computer Science&Technology,BUPTPumping 引理的应用引理
29、的应用（用于证明某个语言用于证明某个语言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，
30、k为常数，为常数，取取i=0，有有1002=12=an-kbn，此此时时，a，b字字符符个个数数不不同同,即新组成的串即新组成的串12 L.与假设矛盾，故与假设矛盾，故L不是正则集不是正则集.372022/12/25College of Computer Science&Technology,BUPTPumping 引理的应用引理的应用 例例 证明证明kk的整数不是正则集的整数不是正则集.证明证明假设假设L是正则集，取足够大的整数是正则集，取足够大的整数n，.有有102=n2n，00n，010n取取i=2，有有n21022n2+n(n+1)2 10i2(串长不是整数的平方串长不是整数的平方)与假设矛盾。与假设矛盾。L不是正则集。不是正则集。382022/12/25College of Computer Science&Technology,BUPT课后练习课后练习 转换下列正则表达式为带转换下列正则表达式为带 转移的转移的NFANFA.a)01*.b)(0+1)01.c)00(0+1)*.Chap3 习题习题5，7，17