形式语言与自动机week4-ch3.7-3.9a

1、1College of Computer Science & Technology, BUPT 正则表达式与有限自动机的关系正则表达式与有限自动机的关系 右线性语言与有限自动机的关系右线性语言与有限自动机的关系 右线性语言的性质右线性语言的性质(part1)第四讲第四讲2College of Computer Science & Technology, BUPT3.7 正则表达式与有限自动机的关系结论结论: 有限自动机、右（左）线性文法、正则表有限自动机、右（左）线性文法、正则表达式都定义了同一种语言达式都定义了同一种语言- 正则语言正则语言 . 证明策略证明策略 - NFAN

2、FADFARERE( Regular Expression) - 正则表达式3College of Computer Science & Technology, BUPT从从 DFA 构造等价的构造等价的正则表达式正则表达式（状态消去法）（状态消去法）思路思路: : (1) 扩展自动机的概念，允许正则表达式作为转移弧的标记. 这样，就有可能在消去某一中间状态时，保证自动机能够接受的字符串集合保持不变. (2) 在消去某一中间状态时，与其相关的转移弧也将同时消去，所造成的影响将通过修改从每一个前趋状态到每一个后继状态的转移弧标记来弥补. 以下分别介绍中间状态的消去与正则表达式构造过程.4

3、College of Computer Science & Technology, BUPT从从 DFA 构造等价的构造等价的正则表达式正则表达式（中间状态的消去）（中间状态的消去）xy r1r2xz r1y r2代之以：xy r1+r2xyr2r1代之以：xy r1*xz y r1代之以：5College of Computer Science & Technology, BUPT从从 DFA 构造等价的构造等价的正则表达式正则表达式（中间状态的消去）（中间状态的消去）sSq1qkp1pmP1PmQkQ1R11R1mRkmRk1R11+ Q1S* P1R1m+ Q1S* Pm

4、Rkm+ QkS* PmRk1 + QkS* P1q1p1qkpm消去消去 s6College of Computer Science & Technology, BUPT从从 DFA 构造等价的构造等价的正则表达式正则表达式（状态消去法）（状态消去法）步骤步骤: : (1) 对每一终态对每一终态q，依次消去除依次消去除 q 和初态和初态 q0 之外的其它状态之外的其它状态; ;StartRStartSTUR(2) 若若q q0，最终可得到一般最终可得到一般形式如下左图形式如下左图两状态自动机，两状态自动机， 该自动机对应的正则表达式可表示为该自动机对应的正则表达式可表示为 ( R+S

5、U*T )*SU*.(3) 若若q= q0，最终可得到最终可得到如下右图的自动机，它对应的正则如下右图的自动机，它对应的正则 表达式可以表示为表达式可以表示为 R*.(4) 最终最终的正则表达式为的正则表达式为每一终态对应的每一终态对应的 正则表达式之和（并）正则表达式之和（并）.7College of Computer Science & Technology, BUPT状态消去法举例状态消去法举例A0+1StartBCD10+10+1对于终态对于终态CA0+1StartC1(0+1)A0+1StartD1(0+1)(0+1)对于终态对于终态D等价的正则表达式等价的正则表达式(0+1

6、)*1(0+1)+(0+1)*1(0+1)(0+1)8College 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)*9College of Computer Science & Technology, BUPT定理定理: L 是正则表达式是正则表达式 R 表示的语言表示的语言, 则存在一个则存在一个 - NFA E ,满足满足 L(E) = L(R) =

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

8、对于对于 a ，构造为构造为a2 对于对于 ，构造为构造为11College of Computer Science & Technology, BUPT归纳归纳: :从从正则表达式正则表达式构造等价的构造等价的 - NFA（归纳归纳构造过程）构造过程）1 对于对于 R+S ，构造为构造为SR 12College of Computer Science & Technology, BUPT归纳归纳: :从从正则表达式正则表达式构造等价的构造等价的 - NFA（归纳归纳构造过程）构造过程）2 对于对于 RS ，构造为构造为RS R3 对于对于 R* ，构造为构造为 13Colle

9、ge of Computer Science & Technology, BUPT举例举例: : 设设正则表达式正则表达式 1*0(0+1)*, 构造等价的构造等价的 - NFA.从从正则表达式正则表达式构造等价的构造等价的 - NFA100+1 11* 14College of Computer Science & Technology, BUPT从从正则表达式正则表达式构造等价的构造等价的 - NFA(0+1)*10 11001*0(0+1)* 15College of Computer Science & Technology, BUPT3.8 右线性语言与右线性

10、语言与有限自动机有限自动机 至此，我们已学到正则集有三种定义方式，且这三种方式等价： 正则集是含有，a 以及在并、连接和 * 运算下封闭的语言 由正规表达式定义的集合是正则集。 由右线性文法生成的语言是正则集。此外，还有第四种方式： 将正则集作为由有限自动机定义的集合。即 正则集(右线性语言) 有限自动机16College of Computer Science & Technology, BUPT右线性文法右线性文法 有限自动机有限自动机定理定理3.8.1：由任意右线性文法G定义的语言必然能被一个NFA M所接受。即L（G）L（M）证明思路（构造证明）证明思路（构造证明）：设右线性文

11、法G（N，T，P，S），构造一个与G等价的有限自动机NFA M（Q，T，q0，F），其中： QN U H，H为一个新增加的状态, HN， q0S H，S 当S-属于P。 H 否则 的定义为：的定义为：当当A a B P，则则 B （A，a）当当A a P, 则则 H （A，a）对于任意输入，（H，a）。F=17College of Computer Science & Technology, BUPT右线性文法右线性文法 有限自动机有限自动机（例）例：例：设有右线性文法设有右线性文法G=(S,B ,a,b, P,S)，其中其中P： SaB BaB|bS|a 试构造与试构造与G等价的有限

12、自动机等价的有限自动机M。解：解： 设设NFA M=(Q,T, , q0, F)Q=S,B,H T=a,b q0 = S F =H转换函数转换函数 ：n对于产生式对于产生式SaB，有有(S,a)=Bn对于产生式对于产生式BaB，有有(B,a)=Bn对于产生式对于产生式BbS，有有(B,b)=Sn对于产生式对于产生式Ba， 有有(B,a)=HSBH开始aaab18College of Computer Science & Technology, BUPT右线性文法右线性文法 有限自动机有限自动机（续）（续）求证求证 G与与NFA M两者定义了同一语言。两者定义了同一语言。 证明：证明：

13、先证（先证（1）文法）文法G产生的语言产生的语言 L(G) 能够被能够被NFA M所接收；所接收；再证（再证（2）NFA M 接受的语言接受的语言 L(M) 可由文法可由文法G 产生。产生。19College of Computer Science & Technology, BUPT右线性文法右线性文法 有限自动机有限自动机（续）（续）证明方法：证明方法：通过两者定义的语言中任意一个字符串来说明。（1）设 = a1a2anL(G) ，且n 1则有 S a1A1 a1a2A2 a1a2an-1An-1 a1a2 an-1a n则由的定义，有A1 (S，a1)，A2 (A1，a2), ,

14、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）。 #20College of Computer Science & Technology, BUPT右线性文法右线性文法 有限自动机有限自动机（续）（续）（2）再证再证 L(M)可由可由G产生产生设 = a1a2an 被NFA M接受，即 L（M），则必然存在状态序列 S， A1，A2 ， An-1，H对M有转换函

15、数为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）。）。 #21College of Computer Science & Technology, BUPT课堂练习：课堂练习：练习：练习： 设线性文法设线性文法 G （S，A，B，a，b，P，S） P： S aA | baB | aA aA | aS | bBB b

16、B | b | a构造相应的构造相应的 NFA M。22College 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

17、， Sq0P定义为：定义为： 若若（A，a）B 且且 B F，则则A aB 在在P中中 若若（A，a）B 且且 B F，则则A a 和和A aB 在在P中中 （注：书上未明确）（注：书上未明确） L（M） L（G） 的证明见书的证明见书 P91 （自学）。自学）。 23College of Computer Science & Technology, BUPT有限自动机有限自动机右线性文法右线性文法（例）例：例：设有设有DFA M =(q0,q1,q2,q3, a,b, , q0, q3 ) 其中转换函数如图所示，其中转换函数如图所示， 试构造与之等价的右线性文法试构造与之等价的右线性

18、文法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

19、,b, P,q,a,b, P,q0 0) )P： q0aq0|bq2 q1a|bq1 q2aq2|b24College of Computer Science & Technology, BUPT3.9 右线性语言的性质右线性语言的性质主要内容：主要内容：DFA的极小化泵浦引理右线性语言的封闭性25College of Computer Science & Technology, BUPT确定有限自动机确定有限自动机DFA的化简的化简(极小化极小化)对DFA M的极小化是找出一个状态数比M少的DFA M1，使满足 L(M) = L(M1) 1等价和可区分的概念 设DFA M =

20、 (Q，T，q0，F) 对不同的状态q， qQ 和每个T*，如果有(q，)* (q，) 必有 (q，)* (q，) 且qF，则称q与q状态等价. 记为qq 否则，称q， q可区分. 26College of Computer Science & Technology, BUPT确定有限自动机确定有限自动机DFA的化简的化简2不可达状态 如果不存在任何T*，使(q，)* (q，)， 则称状态qQ为不可达状态.3 最小化 若DFA 不存在互为等价状态及不可达状态，则称DFA 是最小化的.27College of Computer Science & Technology, BUPT

21、最小化算法最小化算法 一个DFA 的最小化，是把的状态集构成一个划分。即: 任何两个子集的状态都是可区分的；同一子集中的任何两个状态都是等价的。之后，每个子集用一个状态代表，并取一个状态名.构成划分的步骤构成划分的步骤: 构成基本划分 =，”， (为终态集，”为非终态集) 细分 =1， 2， n， i i = q， q， q当输入任意字符a时，若i中的状态经标a的边可到达的状态集的元素分属于两个不同的子集中，则将i 细分为两个子集.重复步骤(2)，直至不可再细分，得到1.若1中有不可达状态，将其删除，1便是最小化的. 28College of Computer Science & Te

22、chnology, 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)= q q， q 同一子集.对字符b，有(q，b)= q，(q，a)= q q， q 同一子集. = q， q 不能再细分. 可用q表示 状态.(b) 对于” = q， q， q对a，(q,a)= q，(q,a)= q，(q,a)= q q, q同一子集对b，(q,b)= q，(q,b)= q，(q,b)= q q， q， q 同一子集. 将再分解. = q， q1，q3 ，q1

23、，q3 不可再细分，用q1表示 q，q，q 29College of Computer Science & Technology, BUPT计算状态集划分的算法计算状态集划分的算法 填表法填表法 填表算法（填表算法（table-filling algorithm）基于如下递归地基于如下递归地 标记可区分的状态偶对的过程标记可区分的状态偶对的过程:- 基础基础 如果如果 p 为终态，而为终态，而 q 为非终态，则为非终态，则 p 和和 q 标记标记 为可区分的；为可区分的；- 归纳归纳 设设 p 和和 q 已标记为可区分的已标记为可区分的, 如果状态如果状态 r 和和 s 通过某个通过某

24、个 输入符号输入符号 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) ）30College of Computer Science & Technology, BUPT计算状态集划分的算法计算状态集划分的算法 填表法填表法 填表算法举例填表算法举例212334455667xxxxx

25、xxxxxxxx651Start3724aaaaaaabbbbbbb(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,731College of Computer Science & Technology, BUPT通过合并等价的状态进行通过合并等价的状态进行 DFA 的优化的优化 步骤步骤 1. 删除所有从开始状态不可到达的状态及与其相关的边删除所有从开始状态不可到达的状态及与其相

26、关的边, 设所得到的设所得到的 DFA 为为 A = (Q, T, , q0 , F ) ； 2. 使用填表算法找出所有等价的状态偶对；使用填表算法找出所有等价的状态偶对； 3. 根据根据 2 的结果计算当前状态集合的划分块，每一划分的结果计算当前状态集合的划分块，每一划分 块中的状态相互之间等价，而不同划分块中的状态之块中的状态相互之间等价，而不同划分块中的状态之 间都是可区分的间都是可区分的. 包含状态包含状态 q 的划分块用的划分块用 q 表示表示. 4. 构造与构造与 A 等价的等价的 DFA B = (QB, T, B, q0, FB ) , 其中其中 QB= q | q Q, FB

27、 = q | q F, B(q ,a)= (q,a)32College of Computer Science & Technology, BUPT通过合并等价的状态进行通过合并等价的状态进行 DFA 的优化的优化 举例举例 651Start3724aaaaaaabbbbbbb 划分结果：划分结果： 1, 2 , 3, 4, 5, 6, 7 等价的状态偶对为：等价的状态偶对为： （1, 2）,（6, 7） 新的状态集合：新的状态集合： 1, 3, 4, 5, 6651Start34aaaabbbbba33College of Computer Science & Technol

28、ogy, BUPT最小化的最小化的 DFA 课堂练习课堂练习 最小化下列最小化下列 DFA:651Start3724aaaaaaabbbbbbb 参考结果参考结果61Start34aaaabbbb34College of Computer Science & Technology, BUPT针对正则语言的针对正则语言的 Pumping 引理引理 正则语言应满足的一个必要条件 用于判定给定的语言不是正则集。物理意义：物理意义：当给定一个正则集和该集合上一个足够长的字符串时，在该字符串中能找到一个非空的子串，并使子串重复，从而组成新的字符串。该新串必在同一个正则集内。定理：定理：设L是正则

29、集，存在常数n，对字符串 且n，则可写成10，其中10n， 0，对所有的0有10i2。证明证明 设设 L 是是 DFA D = (Q, T, , q0 , F ) 的语言，的语言， 取取 n = |Q| 即可即可. 35College of Computer Science & Technology, BUPTDFA 的的“Pumping”特性特性 设 DFA D = (Q, T, , q0 , F ), |Q|=n. 对于任一长度不小于 n 的字符串 w = a1a2am , 其中 mn, akT (1 k m), qQ , 考察如下状态序列 p0=q p1=(q, a1) p2=(

30、q, a1a2) pn=(q, a1a2an ) pn+1=(q, a1a2an+1 ) pm=(q, a1a2am ) 由pigeonhole 原理, p0, p1, p2, , pn 中至少有两个状态是重复的，即存在 i, j, 0ijn, pi=pj . “pumping” 特性： 任一长度不小于状态数目 的字符串所标记的路径上， 必然出现重复的状态.36College of Computer Science & Technology, BUPTDFA 的的“Pumping”特性特性 “pumping” 特性：特性：如前如前,设设 DFA D = (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