《形式语言与自动机ch3.7-3.9a剖析.》由会员分享，可在线阅读，更多相关《形式语言与自动机ch3.7-3.9a剖析.（39页珍藏版）》请在金锄头文库上搜索。
1、1,College of Computer Science & Technology, BUPT,正则表达式与有限自动机的关系 右线性语言与有限自动机的关系 右线性语言的性质(part1),第四讲,2,College of Computer Science & Technology, BUPT,3.7 正则表达式与有限自动机的关系,结论: 有限自动机、右（左）线性文法、正则表达式都定义了同一种语言- 正则语言 .,证明策略,RE( Regular Expression) - 正则表达式,3,College of Computer Science & Technology, BUPT,从 DFA
2、 构造等价的正则表达式 （状态消去法）,思路: (1) 扩展自动机的概念，允许正则表达式作为转移弧的标记. 这样，就有可能在消去某一中间状态时，保证自动机能够接受的字符串集合保持不变. (2) 在消去某一中间状态时，与其相关的转移弧也将同时消去，所造成的影响将通过修改从每一个前趋状态到每一个后继状态的转移弧标记来弥补. 以下分别介绍中间状态的消去与正则表达式构造过程.,4,College of Computer Science & Technology, BUPT,从 DFA 构造等价的正则表达式 （中间状态的消去）,5,College of Computer Science & Techno
3、logy, BUPT,从 DFA 构造等价的正则表达式 （中间状态的消去）,6,College of Computer Science & Technology, BUPT,从 DFA 构造等价的正则表达式 （状态消去法）,步骤: (1) 对每一终态q，依次消去除 q 和初态 q0 之外的其它状态;,(2) 若q q0，最终可得到一般形式如下左图两状态自动机， 该自动机对应的正则表达式可表示为 ( R+SU*T )*SU*.,(3) 若q= q0，最终可得到如下右图的自动机，它对应的正则 表达式可以表示为 R*.,(4) 最终的正则表达式为每一终态对应的 正则表达式之和（并）.,7,Colle
4、ge of Computer Science & Technology, BUPT,状态消去法举例,对于终态C,对于终态D,8,College of Computer Science & Technology, BUPT,状态消去法举例,9,College of Computer Science & Technology, BUPT,定理: L 是正则表达式 R 表示的语言, 则存在一个 - NFA E ,满足 L(E) = L(R) = L. 证明: 构造性证明. 可以通过结构归纳法证明从 R 可以构造出与其等价的，满足如下条件的 - NFA ： (1) 恰好一个终态; (2) 没有弧进入初
5、态； (3) 没有弧离开终态； ,从正则表达式构造等价的 - NFA,10,College of Computer Science & Technology, BUPT,基础:,从正则表达式构造等价的 - NFA （归纳构造过程）,2 对于 ，构造为,11,College of Computer Science & Technology, BUPT,归纳:,从正则表达式构造等价的 - NFA （归纳构造过程）,1 对于 R+S ，构造为,12,College of Computer Science & Technology, BUPT,归纳:,从正则表达式构造等价的 - NFA （归纳构造过程
6、）,13,College of Computer Science & Technology, BUPT,举例: 设正则表达式 1*0(0+1)*, 构造等价的 - NFA.,从正则表达式构造等价的 - NFA,14,College of Computer Science & Technology, BUPT,从正则表达式构造等价的 - NFA,15,College of Computer Science & Technology, BUPT,3.8 右线性语言与有限自动机,至此，我们已学到正则集有三种定义方式，且这三种方式等价： 正则集是含有，a 以及在并、连接和 * 运算下封闭的语言 由正规
7、表达式定义的集合是正则集。 由右线性文法生成的语言是正则集。 此外，还有第四种方式： 将正则集作为由有限自动机定义的集合。 即 正则集(右线性语言) 有限自动机,16,College of Computer Science & Technology, 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 当S-属于P。 H 否则 的定义
8、为： 当A a B P，则 B （A，a） 当A a P, 则 H （A，a） 对于任意输入，（H，a）。,17,College of Computer Science & Technology, 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 转换函数： 对于产生式SaB，有(S,a)=B 对于产生式BaB，有(B,a)=B 对于产生式BbS，有(B,b)=S 对于产生式Ba，
9、 有(B,a)=H,18,College of Computer Science & Technology, BUPT,右线性文法 有限自动机（续）,求证 G与NFA M两者定义了同一语言。 证明： 先证（1）文法G产生的语言 L(G) 能够被NFA M所接收； 再证（2）NFA M 接受的语言 L(M) 可由文法G 产生。,19,College of Computer Science & Technology, BUPT,右线性文法 有限自动机（续）,证明方法：通过两者定义的语言中任意一个字符串来说明。 （1）设 = a1a2anL(G) ，且n 1 则有 S a1A1 a1a2A2 a1a
10、2an-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）。 #,20,College of Computer Science & Technology, BUPT,右线性文法 有限自动机（续）,（2）再证 L(M)可由G产生 设 = a1a2an 被NFA M接受，即 L（M）， 则必然存在
11、状态序列 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）。 #,21,College of Computer Science & Technology, BUPT,课堂练习：,练习： 设线性文法 G （S，A，B，a，b，P，S） P： S aA | baB
12、| a A aA | aS | bB B bB | b | a 构造相应的 NFA M。,22,College of Computer Science & Technology, 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， Sq0 P定义为： 若（A，a）B 且 B F，则A aB 在P中 若（A，a）B 且 B F，则A a 和A aB
13、 在P中 （注：书上未明确） L（M） L（G） 的证明见书 P91 （自学）。,23,College of Computer Science & Technology, BUPT,有限自动机右线性文法（例）,例：设有DFA M =(q0,q1,q2,q3, a,b, , q0, q3 ) 其中转换函数如图所示， 试构造与之等价的右线性文法G。,解：构造右线性文法G=(N,T,P,S) N =q0,q1,q2,q3 T =a,b S = q0 产生式集合P (q0,a)=q1， q0aq1 (q0,b)=q2， q0bq2 (q1,a)=q3，q3F， q1a|aq3 (q1,b)=q1， q
14、1bq1 (q2,a)=q2， q2aq2 (q2,b)=q3，q3F， q2b|bq3,构造的文法G(化简q3)： G=(q0,q1,q2,a,b, P,q0) P： q0aq0|bq2 q1a|bq1 q2aq2|b,24,College of Computer Science & Technology, BUPT,3.9 右线性语言的性质,主要内容： DFA的极小化 泵浦引理 右线性语言的封闭性,25,College of Computer Science & Technology, BUPT,确定有限自动机DFA的化简(极小化),对DFA M的极小化是找出一个状态数比M少的DFA M1
15、，使满足 L(M) = L(M1) 1等价和可区分的概念 设DFA M = (Q，T，q0，F) 对不同的状态q， qQ 和每个T*， 如果有 (q，)* (q，) 必有 (q，)* (q，) 且qF， 则称q与q状态等价. 记为qq 否则，称q， q可区分.,26,College of Computer Science & Technology, BUPT,确定有限自动机DFA的化简,2不可达状态 如果不存在任何T*，使(q，)* (q，)， 则称状态qQ为不可达状态. 3 最小化 若DFA 不存在互为等价状态及不可达状态，则称DFA 是最小化的.,27,College of Computer Science & Technology, BUPT,最小化算法,一个DFA 的最小化，是把的状态集构成一个划分。 即: 任何两个子集的状态都是可区分的；同一子集中的任何两个状态都是等价的。之后，每个子集用一个状态代表，并取一个状态名. 构成划分的步骤: 构成基本划分 =，”， (为终态集，”为非终态集
