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

1、12021-7-12College of Computer Science ; Start R Start S T U R (2) 若若q q0，最终可得到一般最终可得到一般形式如下左图形式如下左图的状态自动机，的状态自动机， 该自动机对应的正则表达式可表示为该自动机对应的正则表达式可表示为 ( R+SU*T )*SU*. (3) 若若q= q0，最终可得到最终可得到如下右图的自动机，它对应的正则如下右图的自动机，它对应的正则 表达式可以表示为表达式可以表示为 R*. (4) 最终最终的正则表达式为的正则表达式为每一终态对应的每一终态对应的 正则表达式之和（并）正则表达式之和（并）. 7202

2、1-7-12College of Computer Science (2) 没有弧进入初态；没有弧进入初态； (3) 没有弧离开终态；没有弧离开终态； 从从正则表达式正则表达式构造等价的构造等价的 - NFA 102021-7-12College of Computer Science & Technology, BUPT 基础基础: : 从从正则表达式正则表达式构造等价的构造等价的 - NFA （归纳归纳构造过程）构造过程） 1 对于对于 ，构造为构造为 3 对于对于 a ，构造为构造为a 2 对于对于 ，构造为构造为 112021-7-12College of Computer Scien

3、ce & Technology, BUPT 归纳归纳: : 从从正则表达式正则表达式构造等价的构造等价的 - NFA （归纳归纳构造过程）构造过程） 1 对于对于 R+S ，构造为构造为 S R 122021-7-12College of Computer Science & Technology, BUPT 归纳归纳: : 从从正则表达式正则表达式构造等价的构造等价的 - NFA （归纳归纳构造过程）构造过程） 2 对于对于 RS ，构造为构造为 RS R 3 对于对于 R* ，构造为构造为 132021-7-12College of Computer Science & Technolog

4、y, BUPT 举例举例: : 设设正则表达式正则表达式 1*0(0+1)*, 构造等价的构造等价的 - NFA. 从从正则表达式正则表达式构造等价的构造等价的 - NFA 1 0 0+1 1 1* 142021-7-12College of Computer Science & Technology, BUPT 从从正则表达式正则表达式构造等价的构造等价的 - NFA (0+1)* 1 0 1 1 0 0 1*0(0+1)* 152021-7-12College of Computer Science & Technology, BUPT 3.8 右线性语言与右线性语言与有限自动机有限自动机

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

6、法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= 172021-7-12College of Computer Science & Technology, BUPT 右线性文法右线性文法 有限自动机有限自动机（例） 例：例：设有右线性文法设有右线性文法G=(S,B ,a,b, P,S)，其中其中 P： SaB BaB|bS|a

7、试构造与试构造与G等价的有限自动机等价的有限自动机M。 解：解： 设设NFA M=(Q,T, , q0, F) Q=S,B,H T=a,b q0 = S F =H 转换函数转换函数 ： n对于产生式对于产生式SaB，有有(S,a)=B n对于产生式对于产生式BaB，有有(B,a)=B n对于产生式对于产生式BbS，有有(B,b)=S n对于产生式对于产生式Ba， 有有(B,a)=H SBH 开始 a a a b 182021-7-12College of Computer Science & Technology, BUPT 右线性文法右线性文法 有限自动机有限自动机（续）（续） 求证求证 G

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

9、n-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）。 # 202021-7-12College of Computer Science & Technology, BUPT 右线性文法右线性文法 有限自动机有限自动机（续）（续） （2）再证再证 L(M)可由可由G产生产

10、生 设 = 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）。）。 # 212021-7-12College of Computer Science & Technology, BUPT 课

11、堂练习：课堂练习： 练习：练习： 设线性文法设线性文法 G （S，A，B，a，b，P，S） P： S aA | baB | a A aA | aS | bB B bB | b | a 构造相应的构造相应的 NFA M。 222021-7-12College of Computer Science & Technology, BUPT 有限自动机有限自动机 右线性文法右线性文法 定理定理3.8.2：设有限自动机设有限自动机 M 接受的语言为接受的语言为L(M) 则存在右线性文法则存在右线性文法G，它产生的语言它产生的语言L(G)L(M)。 证明思路：证明思路： 构造一个右线性文法构造一个右线性文

12、法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 在在P中中 （注：书上未明确）（注：书上未明确） L（M） L（G） 的证明见书的证明见书 P91 （自学）。自学）。 232021-7-12College of Computer Science & Technology, BUPT 有限自动机有限自动机右

13、线性文法右线性文法（例） 例：例：设有设有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， q1bq

14、1 (q2,a)=q2， q2aq2 (q2,b)=q3，q3F， q2b|bq3 q0 q1 q2 q3 a a a bb b 开始 构造的文法构造的文法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 242021-7-12College of Computer Science & Technology, BUPT 3.9 右线性语言的性质右线性语言的性质 主要内容：主要内容： DFA的极小化 泵浦引理 右线性语言的封闭性 252021-7-12

15、College of Computer Science & Technology, BUPT 确定有限自动机确定有限自动机DFA的化简的化简(极小化极小化) 对DFA M的极小化是找出一个状态数比M少的 DFA M1，使满足 L(M) = L(M1) 1等价和可区分的概念 设DFA M = (Q，T，q0，F) 对不同的状态q， qQ 和每个T*， 如果有 (q，)* (q，) 必有 (q，)* (q，) 且qF， 则称q与q状态等价. 记为qq 否则，称q， q可区分。 262021-7-12College of Computer Science & Technology, BUPT 确定有

16、限自动机确定有限自动机DFA的化简的化简 2不可达状态 如果不存在任何T*，使(q，)* (q，)， 则称状态qQ为不可达状态。 3 最小化 若DFA 不存在互为等价状态及不可达状态，则称 DFA 是最小化的。 272021-7-12College of Computer Science & Technology, BUPT 最小化算法最小化算法 一个DFA 的最小化，是把的状态集构成一个划分。即: 任 何两个子集的状态都是可区分的；同一子集中的任何两个状态都 是等价的。之后，每个子集用一个状态代表，并取一个状态名。 构成划分的步骤构成划分的步骤: 构成基本划分 =，”， (为终态集，”为非终

17、态 集) 细分 =1， 2， n， i i = q， q， q 当输入任意字符a时，若i中的状态经标a的边可到达的状态集的 元素分属于两个不同的子集中，则将i 细分为两个子集. 重复步骤(2)，直至不可再细分，得到1. 若1中有不可达状态，将其删除，1便是最小化的. 282021-7-12College 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)= q q， q

18、同一子集. 对字符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，q3 不可再细分，用 q1表示 q，q，q 292021-7-12College of Computer Science & Technology, BUPT 计算状态集划分的算法计算状态集划分的算法 填表法填表法 填表算法（

19、填表算法（table-filling algorithm）基于如下递归地基于如下递归地 标记可区别的状态偶对的过程标记可区别的状态偶对的过程: - 基础基础 如果如果 p 为终态，而为终态，而 q 为非终态，则为非终态，则 p 和和 q 标记标记 为可区别的；为可区别的； - 归纳归纳 设设 p 和和 q 已标记为可区别的已标记为可区别的, 如果状态如果状态 r 和和 s 通过某个通过某个 输入符号输入符号 a 可分别转移到可分别转移到 p 和和 q ，即即 (r,a)=p , (s,a)=q , 则则 r 和和 s 也标记为可区别的；也标记为可区别的； 这是因为：这是因为：若若 p 和和 q

20、 可为字符串可为字符串 w 区别区别, 则则 r 和和 s 可可 为字符串为字符串 aw 区别区别. （ (r,aw) = (p,w) , (s,aw) = (q,w) ） 302021-7-12College of Computer Science & Technology, BUPT 计算状态集划分的算法计算状态集划分的算法 填表法填表法 填表算法举例填表算法举例 2 123 3 4 4 5 5 6 6 7 x xxxx xxxx xxxx 6 51 Start 3 7 2 4 a a a a a a a b b b b b b b (1) 区别所有终态和非终态区别所有终态和非终态 (2)

21、 区别区别(1,3), (1,4), (2,3), (2,4), (5,6), (5,7) x x x x x (3) 区别区别 (3,4) x (4) 结束结束. 划分结果：划分结果：1,2, 3, 4, 5, 6,7 312021-7-12College of Computer Science & Technology, BUPT 通过合并等价的状态进行通过合并等价的状态进行 DFA 的优化的优化 步骤步骤 1. 删除所有从开始状态不可到达的状态及与其相关的边删除所有从开始状态不可到达的状态及与其相关的边, 设所得到的设所得到的 DFA 为为 A = (Q, T, , q0 , F ) ；

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

23、of Computer Science & Technology, BUPT 通过合并等价的状态进行通过合并等价的状态进行 DFA 的优化的优化 举例举例 6 51 Start 3 7 2 4 a a a a a a a b b b b b b b 划分结果：划分结果： 1, 2 , 3, 4, 5, 6, 7 等价的状态偶对为：等价的状态偶对为： （1, 2）,（6, 7） 新的状态集合：新的状态集合： 1, 3, 4, 5, 6 6 5 1 Start 3 4a a a a b b b b b a 332021-7-12College of Computer Science & Techn

24、ology, BUPT 最小化的最小化的 DFA 课堂练习课堂练习 最小化下列最小化下列 DFA: 6 51 Start 3 7 2 4 a a a a a a a b b b b b b b 参考结果参考结果 6 1 Start 3 4 a a a a b b bb 342021-7-12College of Computer Science & Technology, BUPT 针对正则语言的针对正则语言的 Pumping 引理引理 正则语言应满足的一个必要条件 用于判定给定的语言不是正则集。 物理意义：物理意义：当给定一个正则集和该集合上一个足够长的字符串 时，在该字符串中能找到一个非空

25、的子串，并使子串重复，从 而组成新的字符串。该新串必在同一个正则集内。 定理：定理： 设L是正则集，存在常数k，对字符串 且 ，则可写成10，其中10， 0 ，对所有的0有10i2。 证明证明 设设 L 是是 DFA D = (Q, T, , q0 , F ) 的语言，的语言， 取取 k = |Q| 即可即可. 352021-7-12College of Computer Science & Technology, BUPT DFA 的的“Pumping”特性特性 设 DFA D = (Q, T, , q0 , F ), |Q|=n. 对于任一长度不小于 n 的字符串 w = a1a2am ,

26、 其中 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” 特性： 任一长度不小于状态数目 的字符串所标记的路径上， 必然出现重复的状态. 362021-7-12College of Computer Science & Technology, BUPT DFA 的

27、的“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 , z = aj+1aj+2am 则对任何则对任何k 0，都有都有 xykz L(D). (参考下图参考下图) Start p0pipm x = a1a2ai y = ai+1ai+2aj z=aj+1aj+2am 372021-7-12C