形式语言与自动机：第08讲-正则语言的性质

1、形式语言与自动机Formal Languages and Automata Theory第五章 正则语言的性质几种语言模型之间的关系：简单回顾上节课的内容：RGDFARENFA图解法分别构造自动机添加终止态Z对AaB|a特殊处理每一个中间状态都是非终结符问题：是否能够构造一个有穷自动机，识别语言：看一个例子：Sq0q1q201有什么办法帮助我们更容易的判别一个语言是否是正则语言？第五章 正则语言的性质正则语言的泵引理正则语言运算的封闭性自动机的极小化正则语言的判定算法*分析：1、识别 RL 句子的 DFA 仅有有限个状态。2、用 DFA M 接受无穷语言 L，L 中一定存在一个足够长的句子，使

2、得 DFA 在识别该句子时，需要重复地经过某些状态。DFA处理句子经历的状态序列DFA处理句子经历的重复状态序列正则语言的泵引理正则语言的泵引理1、假设 L 是 RL，DFA M = ， 满足 L( M ) = L， M 具有有限个状态，即，| Q | = N，且 Q 中状态均为可达状态。2、取 L 中任意句子 z = a1a2am ( m N )，并有 qm F。3、由于 m N ，读字符的状态序列 q0, q1, , qN 中至少有两个状态相同。假设状态 qk = qj, 对于 k j N，有，( q0, a1a2ak ) = qk; ( qk, ak+1 ak+2aj ) = qj =

3、qk; ( qj, aj+1aj+2am ) = qm 对于任意整数 i 0，可能有 ( qk, (ak+1ak+2aj )i ) =( q k, (ak+1ak+2aj )i-1 ) . =( qk, (ak+1ak+2aj ) = qk = qj 泵操作RL 特征的形式化描述：正则语言的泵引理 对任意整数 i 0, ( q0, a1a2ak( ak+1ak+2aj )iaj+1aj+2am ) = qmF亦有： a1a2ak(ak+1ak+2aj )iaj+1aj+2am L（M）设 u = a1a2ak, v = ak+1ak+2aj, w = aj+1aj+2am; 对于任意整数 i

4、0，有： z = uviw L ; 由于 k j N，u, v 应满足条件： | u v | N, | v |1； z 仍然是正则语言 RL 的句子。RL 特征的形式化描述：正则语言的泵引理 定义5-1：泵引理设 L 为 RL，存在仅依赖于语言 L 的某个正整数 N，对于 z L， 如果 | z | N，则存在 u, v, w，满足以下条件：1、z = uvw ;2、| uv | N; 3、| v | 1;4、对于任意整数 i 0，u v i w L。正则语言的泵引理 泵引理应用：用反证法证明给定语言 L 不是 RL。假设 L 是 RL，L 应满足泵引理。构造某句子 z = uvw L，在给定

5、正整数 N 和某个 i 的条件下，可证得句子z = u v i w 不符合语言 L 中句子的结构特征，即有句子 z = u v i w 不属于 RL L。由于 L 中存在句子 z 的结构不满足泵引理 RL 关于 “ 对于任意整数 i 0，u v i w RL L”的描述条件，与假设矛盾，故证得 L 不是 RL。正则语言的泵引理例1：证明语言 L = 0n | n 为素数 不是 RL。证明：假设 L = 0n | n 为素数 是 RL，其满足泵引理。设依赖于 L（M） 的正整数为 N，L 中字符串 z = 0N+p，其中，N + p 是素数。根据泵引理，必存在 u, v, w, 使得 z = u

6、vw 且 | v |1；这里，v 是 0 组成的非空串，不妨设 v = 0k, （k1），w = 0j，u = 0N + p k j，从而有， u vi w = 0N + p k j (0k)i 0j = 0N + p + ( i -1 ) k， 取 i = N + p + 1， N + p + ( i 1 ) k = N + p + ( N + p + 1 - 1) k = ( N + p ) + ( N + p ) k = ( N + p )( 1 + k ) 由于已知 k1， 因此，( N + p )( 1 + k ) 不总是素数。所以，当 i = N + p + 1时，有字符串 z =

7、 uvN + p + 1w = 0( N + p )( 1 + k ) L，其与泵引理第四条矛盾，所以，L 不是 RL。 正则语言的泵引理例2：证明语言 L = 0n1n | n1 不是 RL。证明：假设 L = 0n1n | n1 是 RL，其应满足泵引理。设依赖于 L( M ) 的正整数为 N ，L 中有字符串为 z = 0N1N。根据泵引理，必存在 u, v, w, 构成句子 z = uvw，其中 | uv | N，| v |1；这里，v 只能是由 0 组成的非空串。不失一般性地可设， v = 0k，（k 1），w = 0j 1N， u = 0N k - j，从而有， u vi w =

8、0N k - j (0k)i 0j 1N ，取 i = 2 时，有 u v2 w = 0N k - j (0k)2 0j 1N = 0N + k 1N由于已知 k 1， 有 N N + k,于是有： 字符串 z = 0N + k 1N L，与泵引理第四条矛盾，故 L 不是 RL 正则语言的泵引理正则语言的泵引理1、泵引理给出关于 RL 性质的条件是必要条件：若 L 是 RL，其一定满足泵引理给出的 4 个条件。因此，应用泵引理证明一个语言不是 RL时，常用“反证法” 。2、泵引理给出的 RL 性质的条件不是充分条件；满足泵引理所给 4 个条件的语言不一定就是 RL。因此，泵引理只能用于证明给定

9、语言不是 RL；而不能证明给定语言是 RL。说明：正则语言的泵引理1、给定一个L，如何证明它不是RL。思考：2、给定一个L，如何证明它是RL。正则语言的泵引理正则语言运算的封闭性自动机的极小化正则语言的判定算法*第五章 正则语言的性质定义5-2：如果对某类语言进行某种运算后，所得的结果仍为该类语言的句子，则称该类语言对此运算是封闭的，或称该类语言对运算具有封闭性。正则语言运算的封闭性定义5-3：称某语言类对某运算满足有效封闭性，是指给定该类语言中任意两个语言 L1、L2 的形式化表示，对二语言进行运算后所得语言仍然具有形式化表示算法。正则语言运算的封闭性定理5-1：正则语言 RL 对“并”、“

10、乘积”和“闭包”运算封闭。定理5-2：正则语言 RL 对“补”运算封闭。定理5-3：正则语言 RL 对“交”运算封闭。正则语言运算的封闭性定义4-1：设字母表为 ，正则表达式递归定义如下：正则语言运算的封闭性定理5-1：正则语言对“并”、“乘积”和“闭包”运算封闭。正则语言运算的封闭性对于 r = r1*，构造相应-NFA对于 r = r1r2，构造相应-NFA对于 r = r1 + r2，构造相应-NFA定理5-2： 正则语言 RL 在“补” 运算下是封闭的。证明：设 L 是 上的 RL，则存在 DFA M = ，满足 L（M）= L。取 DFA M = ，显然，对于任意字符串 x *，有

11、( q0, x ) = f F ( q0, x ) = f Q - F 即， x L（M） x L（M） 亦即， L（M） = * - L（M）。正则语言运算的封闭性设 L（ r）= L（Mr），构造与 r 等价的 FA Mr 算法：Mr 的始态作为 Mr 的始态； Mr 与 Mr 的状态转移函数不变；将 Mr 所有非终态 ( 包括陷阱态 qt ) 作为 Mr 的终态；将 Mr 所有终态作为 Mr 的非终态。正则语言运算的封闭性例3：设表达式 r = 00 *11* 等价 FA Mr 如图所示，求与 r 等价的 FA Mr 。q101110,100q1q2q3qtq101110,100p1p2

12、p3p4正则语言运算的封闭性定理5-3：正则语言 RL 在“交” 运算下是封闭的。证明：由 De Morgan 定理：r1r2 = ( r1 r2 ) 和 定理 5-1、5-2 可证正则语言运算的封闭性给定 r1, r2 等价的 DFA M1 = ，DFA M2 = ，构造 DFA M，使得 L( M ) = L( M1 ) L( M2 )。L( r1r2 ) 的 DFA M 构造分析：正则语言运算的封闭性设 L( M1 ) = L( r1 )、L( M2 ) = L( r2 ) ，构造接受 L( r1r2 ) 的 DFA M = 算法：4、若 M1，M2 中含有陷阱态 qt ，对应有序偶为

13、M 的陷阱态 qt。 2、 M 的始态为 M1 和 M2 始态有序偶； M 的终态为 M1和 M2 的终态有序偶； 1、取 = 1 2 ；Q = Q1Q2；对 a ，q i Q1，q j Q2， 定义： ( q i, q j , a ) = 1 ( q i, a ), 2 ( q j, a ) ；3、如果对于输入字符 a，M1 和 M2 中某一状态没有转移状态，则 M 对应的有序偶转向陷阱态 qt；正则语言运算的封闭性2、根据 NFA 求 DFA M 算法： q1, q3 为始态； q2, q3 为终态。2、 M 的状态表。 例4：设 r1= 01* ，r2=(01)* ；求 r = r1r2

14、 等价的 DFA M。q3q401q2q110M1M23、 令 DFA M 状态： p1= q1, q3 -始态, p2 = q2, q4 p3 = q2, q3 -终态，与 r = 01*( 01)* 等价的 DFA M：状态说明状态列输入字符列01始态 q1, q3 q2, q4 qt, qt q2, q4 qt, qt q2, q3 终态 q2, q3 qt, q4 q2, qt 解：1、与 r1 和 r2 等价的 FA M1 和 M2 ：p3p1p201r = 01*( 01)* = 01正则代换（Substitution）：正则语言运算的封闭性同态映射（Homomorphism）：商

15、（quotient）：29正则语言的泵引理正则语言运算的封闭性自动机的极小化正则语言的判定算法*第五章 正则语言性质自动机的极小化问题的引出及 DFA 极小化思路最简自动机求解的相关概念Myhill Nerode （米希尔-尼罗德）定理自动机极小化求解算法与求解实例给定正则语言 L，描述 L 的正则文法 RG 和有穷自动机 FA 的描述本质相同：给定正则语言 L，正则文法 G 或 自动机 DFA 均根据语言的结构特征，对 L 字母表的克林闭包 * 中字符串进行等价划分（分类 )，以求字符串的各个等价类 。 切入点：自动机极小化思路例：L = x000 | x 0,1* x001 | x 0,1

16、 * set (q0) = x | x *, x = 或者 x 以 1 结尾但不以 001 结尾 ;set (q1) = x | x *, x = 0 或者 x 以 10 结尾 set (q2) = x | x *, x = 00 或者 x 以 100 结尾 set (q3) = x | x *, x 以 000 结尾 set (q4) = x | x *, x 以 001 结尾 5 个集合两两互不相交；5 个集合的并构成 M 识别输入字母表 0，1 的克林闭包；5 个集合是关于 0, 1 * 的一个等价划分。自动机极小化思路可知：1）DFA M 的每个可达状态存储一个输入字符子串的等价类，记

17、为 set ( q )自动机极小化思路3） DFA M 的极小化：求解将* 划分形成的等价类个数最少，亦即，用于存储字符子串的状态数最少的自动机。2）对于同一正则语言 L，不同结构的自动机模型对 * 进行的等价划分不同，所得到字符子串的等价类也不尽相同 。自动机极小化思路例：对于 正则语言 L = 0*10*，两种不同结构 DFA 如图所示。自动机的极小化问题的引出及极小化思路最简自动机求解的相关概念Myhill Nerode （米希尔-尼罗德）定理自动机极小化求解算法与求解实例最简自动机求解的相关概念1、 DFA M 对 * 的等价划分2、 语言 L 对 * 的等价划分3、 * 上右不变等价

18、关系4、 * 上的等价指数1、 DFA M 对 * 的等价划分回顾定义 3-4 ：设 DFA M = ，对于 q Q，定义引导 M 从开始状态到达状态 q 对应的输入字符串集合为：set ( q ) = x | x *, ( q0, x ) = q 最简自动机求解的相关概念定义 5-4：设 DFA M = ，M 确定的 * 上的关系 RM 定义为： 对于 x, y *，满足以下等式： x RM y ( q0, x ) = ( q0, y ) = q。1、 DFA M 对 * 的等价划分综合定义 5-4 和 定义 3-4，有： x RM y q Q, x, y set ( q )最简自动机求解的

19、相关概念最简自动机求解的相关概念例6：设 L = 0*10* 对应的 DFA M 如图所示。满足关系 RM 各状态 q 中所存字符串的等价描述：q0： ( 00 )n RM ( 00 )m n, m 0 q1： 0( 00 )n RM 0( 00 )m n, m 0 q2： ( 00 )n1 RM ( 00 )m1 n, m 0 q3： 0( 00 )n1 RM 0( 00 )m1 n, m 0 q4： 0(00 )n10k RM 0(00 )m10h n, m 0; k, h 1 0n10k RM 0m10h n, m 0; k, h 1q5： x RM y 其它至少含两个 1 的 x, y

20、 串定义5-5：设 L *，对于 x, y *，由 L 确定的 *上的关系 RL 定义为： x RL y 对于 z *，x z L y z L 。注：如果 x RL y，则在 x, y 后连接 * 中的任何字符串 z, x z 和 y z 要么同是 L 的句子；要么都不是 L 的句子。2、 语言 L 对 * 的等价划分最简自动机求解的相关概念定义5-6：设 R 是*上的等价关系，对于 x, y *，如果 x R y，对于 z * ，必有 x z R y z 成立，则称 R 是右不变等价关系。3、 * 上的右不变等价关系最简自动机求解的相关概念定理 5-3：对于任意 DFA M = ，M 确定的

21、 * 上的关系 RM 为右不变等价关系。3、 * 上的右不变等价关系最简自动机求解的相关概念证明：1、RM 是等价关系： x, y ， 自反性： x RM x |=| ( q0, x ) =( q0, x ) ； 对称性： x RM y |=| ( q0, x ) =( q0, y ) |=| ( q0, y ) =( q0, x ) = y RM x 传递性： 设 x RM y |=| ( q0, x ) =( q0, y )； y RM z |=| ( q0, y ) =( q0, z ) 由等号 = 的传递性： ( q0, x ) = ( q0, z ) 由RM的定义有： x RM z

22、2、RM 是右不变关系： 设 x RM y，由 RM 定义有：( q0, x ) =( q0, y ) = q； 故对 z ， 有 ( q0, x z ) = ( ( q0, x ) , z ) = ( q, z ) = ( ( q0, y ), z ) = ( q0, y z ) 最简自动机求解的相关概念定理 5-4：对于任意 L * ，L 所确定的 *上的关系 RL 为右不变等价关系。（ 显然 ）3、 * 上的右不变等价关系最简自动机求解的相关概念满足等价关系 RM 的 x, y, 一定满足 x RL(M) y：1、x, y set ( q )，有( q0, x ) =( q0, y )

23、= q， z *, ( q0, xz ) =( q0, x ), z ) =( q, z ) = ( ( q0, y ) , z ) = ( q0, yz ) ( q0, x z ) F ( q0, y z ) F 或者 x z L(M ) y z L(M ) 所以， x R L( M ) y 成立。2、满足等价关系 RL(M) 的字符串不一定满足等价类 RM 。例如， 由于 x = 00 set ( q0 ), y = 0 set ( q1 ), 因此， 00 RM 0 不成立；RM 和 RL（M）确定等价类的联系与区别：DFA M 接受语言 L( M ) = 0*10*然而，若设 z =

24、10， 由于 0010 L( M ) 010 L( M ) ，因此，x, y 满足语言 L( M ) = 0*10* 确定的关系 R L（ M ）： 00 R L( M ) 0 成立 对于任意 DFA M = ，有：1）一般来说，如果 x RM y，一定有 x RL（M） y ；反之，不一定成立。亦即，按照 RM 分类，分在同一等价类中的字符串 x, y，按照 RL(M) 分类时，一定会分在同一等价类中；被 RM 分在不同等价类中的字符串 x, y，按照 RL(M) 分类时，也可能被分在 RL(M) 的同一等价类中。结论：2） 由于 RM 对 * 的划分比 RL(M) 对 * 的划分更细， R

25、M 的多个等价类可对应到 RL( M ) 的一个等价类，因此，称 RM 是对 RL( M ) 的加细最简自动机求解的相关概念最简自动机求解的相关概念设 R 是 * 上的等价关系，将 | * / R | 定义为 R 关于* 的指数，简称为 R 的指数。以下关系成立： | * / RL(M) | | * / RM | | * / RL(M) | | * / RM | |Q|。4、 * 上的 R 指数问题的引出及极小化思路最简自动机求解的相关概念Myhill Nerode （迈希尔-尼罗德）定理自动机极小化求解算法与求解实例自动机的极小化定理 5-5：以下三个命题等价 ： 1） L *是正则语言 R

26、L。 2） L 是 * 上某个右不变等价关系 RM 的有限个等价类的并集。 3） L 确定的等价关系 RL 具有有穷指数 |* / RL|。Myhill Nerode （迈希尔-尼罗德）定理证明 1） 2）： L *是正则语言 L 是 * 上某个右不变等价关系 RM 的有限个等价类的并集。 由于RM 可把 L（M）中的字符串划分成最多 | Q | 个等价类；并且，F Q，故 L（M）是不多于 | Q | 个等价类的并集。由 DFA M = 定义右不变等价关系 RM （已证），满足 对于 x, y ， x RM y 当且仅当 ( q0, x ) = ( q0, y ) 并且 对于 z ，若 x

27、RM y，有( q0, xz ) = ( ( q0, x ) , z ) = ( ( q0, y ), z ) = ( q0, yz ) Myhill Nerode （迈希尔-尼罗德）定理证明 2） 3）：是 * 上某个具有有穷指数的右不变等价关系 RM 等价类的并集 L 确定的等价关系 RL 具有有穷指数 |* / RL |。设 RM 是不是 上一个右不变等价关系，它把 L 划分成有限个等价类的并集。注意到 RL 也是一个右不变等价关系，对于 x, y, z 有 x RM y xz RM yz x z L y z L x RL y 表明 x RM y x RL y；故如若 RM 把 * 划分

28、成 K 个等价类，则 RL 把 * 划分成 不多于 K 个等价类。 Myhill Nerode （迈希尔-尼罗德）定理证明 3） 1）：L 确定的等价关系 RL 具有有穷指数 |* / RL|，可将 L 划分成有限个等价类 L是正则语言，可被一个 DFA 接受。设 L * ，构造识别语言 L 的 DFA M = （Q, , q0, F ）如下：令* 上右不变等价关系 RL 的商集（等价类的集合）为 DFA M 的状态集，即， Q = * / RL = x | x *, y ： y x y RL x = set( q ) 令 DFA 的初始状态和终止状态集：q0 = ；F = x | x L 令

29、 DFA 的状态转移函数：( x , a ) = xa ；其中， x Q， a 如此构造的 M 是接受 L 的 DFA。Myhill Nerode （迈希尔-尼罗德）定理1）RL 将* 划分为有限等价类算法： 给定接受正则语言 L 的 DFA M ，用右不变等价关系 RM 将 * 划分为有限个 等价类，通过合并 set( qi ) ，求得语言 L 确定 RL 划分 * 的有限等价类集合。Myhill Nerode 定理的应用：2）证明一个语言 L 不是 RL：RL 可将 * 划分为无穷个等价类。Myhill Nerode （迈希尔-尼罗德）定理Myhill Nerode 定理例8：对 */RM

30、 = set (q0), set (q1), set (q2), set (q3), set (q4), set (q5) 中元素两两进行考察，通过合并 RM 等价类获得 RL( M ) 的等价类集合，从而，求得最小自动机。1、取 00set ( q0 ), 000 set ( q1 ), 任意 z * ， z 含且仅含一个 1 时， 00z L( M )， 000z L( M ) z 不含1或含多个1 时，00z L( M )，000z L( M )， 所以, 00 z L( M )，000 z L( M ), set( q0 ) 与 set( q1 )可合并为 RL( M ) 同一等价类2

31、、取00set ( q0 ), 001set ( q2 ), 取 z = 1* 有：00z L(M)， 001z L(M)。 所以, set( q0 ) 与 set( q2 )不可合并为 RL(M) 同一等价类同理， set( q0 ) 与 set( q3 )， set( q4 )， set( q5 ) 的等价类都不可合并。设 DFA M 接受语言： L = 0*10*3、取 001 set ( q2 ), 01 set ( q3 ), 任意 z * ， z 不含 1 时， 001 z L(M)， 01 z L(M) z 含 1 时， 001 z L( M )，01 z L( M )， 所以，

32、 001z L( M ) 01z L( M ), set( q2 ), set( q3 ) 可合并。4、取 1set ( q2 ), 10 set ( q4 ), 任意 z * ， z 不含 1 时，1 z L( M )， 10 z L( M ) z 含 1 时， 1 z L( M )，01 z L( M )， 所以， 1 z L( M ) 10 z L( M ), set(q2), set(q4) 可合并。5、取 1 set ( q2 ), 11 set ( q5 ), 设 z =, 有 1 z = 1 = 1，11 z = 11 = 11； 则有, 1 z L( M )； 11 z L(

33、M )，所以，set( q2 ) 与 set( q5 ) 不可合并。设 DFA M 接受语言： L = 0*10*Myhill Nerode 定理*/ RL( M ) = set ( q0 ) set ( q1 ), set ( q2 ) set ( q3 ) set ( q4 ), set ( q5 ) 其中， 不含 1 的串： 0 = set (q0) set (q1) = 0*； 含一个 1 的串： 1 = set ( q2 ) set ( q3 ) set ( q4 ) = 0*10*含多个 1 的串： 11 = set ( q5 ) = 0* 1 0* 1( 0 + 1 )*最小 D

34、FA M：结果：等价关系 RL( M ) 划分 * 的字符串等价类：Myhill Nerode 定理推论 5-1： 对于任意的 RL L，在同构意义下，接受 L 的极小化 DFA 是唯一的。Myhill Nerode （迈希尔-尼罗德）定理58自动机的极小化问题的引出及极小化思路最简自动机求解的相关概念Myhill Nerode （迈希尔-尼罗德）定理自动机极小化求解算法与求解实例方法1：严格按照由 RL 划分 求等价类的定义，从 set ( q ) 和 set ( p ) 中各取一适当的字符串 x, y，利用右不变性质考察：对于任意字符串 z，x z 和 y z 是否同时属于 L 和同时不属

35、于 L。（如前例）评价：1、需要对 M 中任意状态 p、q 两两配对考察；2、计算量与M 中包含状态的个数 | Q | 以及所选字符串 x, y, z 的长度 有关，需要分析 x, y, z 的结构特征。存在两种合并方案：自动机极小化求解算法算法的时间复杂度较高。方法2：1、不考虑哪些状态可以合并，反之，考虑哪些状态不能合并。 - 找出所有不可合并状态，剩下的就是可合并状态；自动机极小化求解算法存在两种合并方案：2、考察从终态往始态方向进行搜索，确定任意两状态是否为不可合并状态。定义 57：设 DFA M = ， 如果 x , 使得 Q 中的两个状态 q 和 p，( q, x ) F 和( p, x ) F 中有且仅有一个成立，则称 q 和 p 是可区分的，否则 q 和 p 等价，记作 q p。自动机极小化求解算法可区分 |=| 不可合并 。命题：设状态 p 和 q 不能合并，对于其它待尚未考察状态 p 和 q，若存在字符 a，使得 ( q, a ) = q, ( p, a ) = p，则可断定状态 p 和 q 也不能合并。自动机极小化算法：输入： 给定的 DFA M = ；1） 对每个 p F，q Q F 的状态对 ( q, p ) 加上可区分标记； /* 标记 p 和 q 不可合并2） 对每个状态对 ( q, p ) F F