1、形式语言与自动机形式语言与自动机Formal Languages and Automata Theory教师教师：胡：胡春明、赵永望春明、赵永望第五章第五章 正则语言的性质正则语言的性质 http:/ 正则语言的性质正则语言的性质正则语言的泵引理正则语言的泵引理正则语言运算的封闭性正则语言运算的封闭性自动机的极小化自动机的极小化正则语言的判定算法正则语言的判定算法*分析分析：1 1、识别、识别 RL RL 句子的句子的 DFA DFA 仅有有限个状态。仅有有限个状态。2 2、用、用 DFA M DFA M 接受无穷语言接受无穷语言 L L，L L 中一定存在一个足够长的句中一定存在一个足够长的
2、句子，使得子，使得 DFA DFA 在识别该句子时，需要重复地经过某些状态。在识别该句子时，需要重复地经过某些状态。DFA处理句子经历处理句子经历的状态序列的状态序列DFA处理句子经历处理句子经历的重复状态序列的重复状态序列正则语言的泵引理正则语言的泵引理正则语言的泵引理正则语言的泵引理1、假设、假设 L 是是 RL，DFA M = ， 满足满足 L( M ) = L， M 具有有限个状态，即，具有有限个状态，即，| Q | = N，且，且 Q 中状态均为可达状态。中状态均为可达状态。2、取、取 L 中任意句子中任意句子 z = a1a2am ( m N )，并有，并有 qm F。3、由于、由
3、于 m N ，读字符的状态序列，读字符的状态序列 q0, q1, , qN 中至少有两个状态相同。中至少有两个状态相同。假设状态假设状态 qk = qj, 对于对于 k j N，有，有，( q0, a1a2ak ) = qk; ( qk, ak+1 ak+2aj ) = qj = 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 特征的形式化描述：特征的形式
4、化描述：正则语言的泵引理正则语言的泵引理 对任意整数对任意整数 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 0，有：有： z = uviw L ; 由于由于 k j N，u, v 应满足条件：应满足条件： | u v | N, | v |1； z 仍然仍然是正则是正则语言语言 RL 的的句子句子。RL 特征的形式化描述：特征的形式化描
5、述：正则语言的泵引理正则语言的泵引理 定义定义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 =
6、 uvw L，在给定正在给定正整数整数 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 为素数为素数 不是不是 R
7、L。证明：假设证明：假设 L = 0n | n 为素数为素数 是是 RL，其满足泵引理。设依赖于，其满足泵引理。设依赖于 L（M） 的正整数为的正整数为 N，L 中字符串中字符串 z = 0N+p，其中，其中，N + p 是素数。是素数。根据泵引理，必存在根据泵引理，必存在 u, v, w, 使得使得 z = uvw 且且 | 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 )
8、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 = uvN + p + 1w = 0( N + p )( 1 + k ) L，其，其与泵引理第四条矛盾，所以，与泵引理第四条矛盾，所以，L 不是不是 RL。 正则语言的泵引理正则语言的泵引理例例2
9、：证明语言：证明语言 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，从而有，
10、从而有， u vi w = 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 个条件。因
11、此，应用泵引理证明一个条件。因此，应用泵引理证明一个语言不是个语言不是 RL时，常用时，常用“反证法反证法” 。2、泵引理给出的、泵引理给出的 RL 性质的条件性质的条件不是充分条件不是充分条件；满足泵引理满足泵引理所给所给 4 个条件的语言个条件的语言不一定就是不一定就是 RL。因此，泵引理。因此，泵引理只能用于只能用于证明给定语言不是证明给定语言不是 RL；而不能证明给定语言是；而不能证明给定语言是 RL。说明：说明：正则语言的泵引理正则语言的泵引理1、给定一个、给定一个L，如何证明它不是，如何证明它不是RL。思考：思考：2、给定一个、给定一个L，如何证明它是，如何证明它是RL。正则语言的
12、泵引理正则语言的泵引理正则语言运算的封闭性正则语言运算的封闭性自动机的极小自动机的极小化化正则语言的判定算法正则语言的判定算法*第五章第五章 正则语言的性质正则语言的性质定义定义5-2：如果对某类语言进行某种运算后，所得的结果仍为该类语言的如果对某类语言进行某种运算后，所得的结果仍为该类语言的句子，则称该类语言对此运算是封闭的，或称该类语言对运算句子，则称该类语言对此运算是封闭的，或称该类语言对运算具有封闭性。具有封闭性。正则语言运算的封闭性正则语言运算的封闭性定义定义5-3：称某语言类对某运算满足有效封闭性，是指给定该类语言中任称某语言类对某运算满足有效封闭性，是指给定该类语言中任意两个语言
13、意两个语言 L1、L2 的形式化表示，对二语言进行运算后所得的形式化表示，对二语言进行运算后所得语言仍然具有形式化表示算法。语言仍然具有形式化表示算法。正则语言运算的封闭性正则语言运算的封闭性定理定理5-1：正则语言正则语言 RL RL 对对“并并”、“乘积乘积”和和“闭包闭包”运算封闭。运算封闭。定理定理5-2：正则语言正则语言 RL RL 对对“补补”运算封闭。运算封闭。定理定理5-3：正则语言正则语言 RL RL 对对“交交”运算封闭。运算封闭。正则语言运算的封闭性正则语言运算的封闭性定义定义4-1：设字母表为设字母表为 ，正则表达式递归定义如下：，正则表达式递归定义如下：正则语言运算的
14、封闭性正则语言运算的封闭性定理定理5-1：正则语言对正则语言对“并并”、“乘积乘积”和和“闭包闭包”运算封闭。运算封闭。正则语言运算的封闭性正则语言运算的封闭性对于对于 r = r1*，构造相应，构造相应-NFA对于对于 r = r1r2，构造相应，构造相应-NFA对于对于 r = r1 + r2，构造相应，构造相应-NFA定理定理5-25-2： 正则语言正则语言 RL RL 在在“补补” ” 运算下是封闭的。运算下是封闭的。证明：证明：设设 L 是是 上的上的 RL，则存在，则存在 DFA M = ，满足，满足 L（M）= L。取。取 DFA M = ，显然，对于任意字符串显然，对于任意字符
15、串 x *，有，有 ( 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 的非终态。的非终态。正则语言运算
16、的封闭性正则语言运算的封闭性例例3：设表达式：设表达式 r = 00 *11* 等价等价 FA Mr 如图所示，求与如图所示，求与 r 等等价的价的 FA Mr 。q101110,100q1q2q3qtq101110,100p1p2p3p4正则语言运算的封闭性正则语言运算的封闭性定理定理5-3：正则语言正则语言 RL RL 在在“交交” ” 运算下是封闭的。运算下是封闭的。证明：证明：由由 De Morgan 定理：定理：r1r2 = ( r1 r2 ) 和和 定理定理 5-1、5-2 可证可证正则语言运算的封闭性正则语言运算的封闭性给定给定 r1, r2 等价的等价的 DFA M1 = ，D
17、FA 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 ，对应有序偶为，对应有序偶为 M 的陷阱态的陷阱态 qt。 2、 M 的始态为的始态为 M1 和和 M2 始态有序偶；始态有序偶； M 的终态为的终态为 M1和和 M2 的终态的终态有序偶
18、；有序偶； 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*
19、 ，r2=(01)* ；求；求 r = r1r2 等价的等价的 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
20、= 01*( 01)* = 01正则代换（正则代换（Substitution）：）：正则语言运算的封闭性正则语言运算的封闭性同态映射（同态映射（Homomorphism）：）：商（商（quotient）：）：29正则语言的泵引理正则语言的泵引理正则语言运算的封闭性正则语言运算的封闭性自动机的极小自动机的极小化化正则语言的判定算法正则语言的判定算法*第五章第五章 正则语言性质正则语言性质自动机的极小化自动机的极小化问题的引出及问题的引出及 DFA 极小化思路极小化思路最简自动机求解的相关概念最简自动机求解的相关概念Myhill Nerode （米希尔（米希尔-尼罗德）定理尼罗德）定理自动机极小化
21、求解算法与求解实例自动机极小化求解算法与求解实例给定正则语言给定正则语言 L，描述，描述 L 的正则文法的正则文法 RG 和有穷自动机和有穷自动机 FA 的描述的描述本质相同：本质相同：给定正则语言给定正则语言 L，正则文法正则文法 G 或或 自动机自动机 DFA 均根据语言均根据语言的结构特征，的结构特征，对对 L 字母表的克林闭包字母表的克林闭包 * 中字符串进行中字符串进行等价划分（分类等价划分（分类 )，以求字符串的各个等价类，以求字符串的各个等价类 。 切入点：切入点：自动机极小化思路自动机极小化思路例：例：L = x000 | x 0,1* x001 | x 0,1 * set (
22、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,
23、1 * 的一个等价划分。的一个等价划分。自动机极小化思路自动机极小化思路可知：可知：1）DFA M 的的每个可达状态存储一个输入字符子串的等价类，记为每个可达状态存储一个输入字符子串的等价类，记为 set ( q )自动机极小化思路自动机极小化思路3） DFA M 的极小化：求解将的极小化：求解将* 划分形成的等价类个数最少，划分形成的等价类个数最少，亦即，用于存储亦即，用于存储字符子串字符子串的状态数最少的自动机。的状态数最少的自动机。2）对于）对于同一正则语言同一正则语言 L，不同结构的自动机模型对不同结构的自动机模型对 * 进行的进行的等价等价划分不同，所得到字符子串的等价类也不尽相同划
24、分不同，所得到字符子串的等价类也不尽相同 。自动机极小化思路自动机极小化思路例：对于例：对于 正则语言正则语言 L = 0*10*，两种，两种不同结构不同结构 DFA 如图所示。如图所示。自动机的极小化自动机的极小化问题的引出及极小化思路问题的引出及极小化思路最简自动机求解的相关概念最简自动机求解的相关概念Myhill Nerode （米希尔（米希尔-尼罗德）定理尼罗德）定理自动机极小化求解算法与求解实例自动机极小化求解算法与求解实例最简自动机求解的相关概念最简自动机求解的相关概念1、 DFA M 对对 * 的等价划分的等价划分2、 语言语言 L 对对 * 的等价划分的等价划分3、 * 上上右
25、不变等价关系右不变等价关系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,
26、x ) = ( q0, y ) = q。1、 DFA M 对对 * 的等价划分的等价划分综合综合定义定义 5-4 和和 定义定义 3-4，有：，有： x RM y q Q, x, y set ( q )最简自动机求解的相关概念最简自动机求解的相关概念最简自动机求解的相关概念最简自动机求解的相关概念例例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：
27、 ( 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 串串定义定义5-5：设设 L *，对于，对于 x, y *，由，由 L 确定的确定的 *上的关系上的关系 RL 定定义为：义为： x RL y 对于对于 z *，x z L y z L 。注：如果注：如果 x RL y，则在，则在 x, y 后连接后连接
28、* 中的任何字符串中的任何字符串 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
29、 M = ，M 确定的确定的 * 上的关上的关系系 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 |=| (
30、q0, y ) =( q0, z ) 由等号由等号 = 的传递性：的传递性： ( q0, x ) = ( q0, z ) 由由RM的定义有：的定义有： x RM z 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 所确定的所确定的 *
31、上的关系上的关系 RL 为右不变等价为右不变等价关系。关系。（ 显然显然 ）3、 * 上的上的右右不变等价关系不变等价关系最简自动机求解的相关概念最简自动机求解的相关概念满足等价关系满足等价关系 RM 的的 x, y, 一定满足一定满足 x RL(M) y：1、x, y set ( q )，有，有( q0, x ) =( q0, y ) = 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
32、 ) 所以，所以， 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 = 10， 由于由于 0010 L( M ) 010 L( M ) ，因此，因此，x, y 满足语言满足语言 L( M ) = 0*10*
33、确定的关系确定的关系 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) 的同一等价类中
34、。的同一等价类中。结论结论：2） 由于由于 RM 对对 * 的划分比的划分比 RL(M) 对对 * 的划分更细，的划分更细， RM 的多个等的多个等价类可对应到价类可对应到 RL( M ) 的一个等价类，因此，称的一个等价类，因此，称 RM 是对是对 RL( M ) 的加细的加细最简自动机求解的相关概念最简自动机求解的相关概念最简自动机求解的相关概念最简自动机求解的相关概念设设 R 是是 * 上的等价关系，将上的等价关系，将 | * / R | 定义为定义为 R 关于关于* 的指数，简的指数，简称为称为 R 的指数。以下关系成立：的指数。以下关系成立： | * / RL(M) | | * /
35、RM | | * / RL(M) | | * / RM | |Q|。4、 * 上的上的 R 指数指数问题的引出及极小化思路问题的引出及极小化思路最简自动机求解的相关概念最简自动机求解的相关概念Myhill Nerode （迈希尔（迈希尔-尼罗德）定理尼罗德）定理自动机极小化求解算法与求解实例自动机极小化求解算法与求解实例自动机的极小化自动机的极小化定理定理 5-5：以下三个命题等价以下三个命题等价 ： 1） L *是正则语言是正则语言 RL。 2） L 是是 * 上上某个右不变等价关系某个右不变等价关系 RM 的有限个等价类的并集。的有限个等价类的并集。 3） L 确定的等价关系确定的等价关系
36、 RL 具有有穷指数具有有穷指数 |* / RL|。()qFsetqMyhill Nerode （迈希尔（迈希尔-尼罗德）定理尼罗德）定理证明证明 1） 2）：）： L *是正则语言是正则语言 L 是是 * 上某个右不变等上某个右不变等价关系价关系 RM 的有限个等价类的并集。的有限个等价类的并集。 由于由于RM 可把可把 L（M）中的字符串划分成最多）中的字符串划分成最多 | Q | 个等价类；并且，个等价类；并且，F Q，故故 L（M）是不多于）是不多于 | Q | 个等价类的并集。个等价类的并集。由由 DFA M = 定义定义右不变等价关系右不变等价关系 RM （已证），满足（已证），满
37、足 对于对于 x, y ， x RM y 当且仅当当且仅当 ( q0, x ) = ( q0, y ) 并且并且 对于对于 z ，若，若 x RM y，有，有( q0, xz ) = ( ( q0, x ) , z ) = ( ( q0, y ), z ) = ( q0, yz ) Myhill Nerode （迈希尔（迈希尔-尼罗德）定理尼罗德）定理证明证明 2） 3）：是）：是 * 上某个具有有穷指数的右不变等价关系上某个具有有穷指数的右不变等价关系 RM 等等价类的并集价类的并集 L 确定的等价关系确定的等价关系 RL 具有有穷指数具有有穷指数 |* / RL |。设设 RM 是不是是不
38、是 上一个右不变等价关系，它把上一个右不变等价关系，它把 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 把把 * 划分成划分成 K 个等价类，则个等价类，则 RL 把把 * 划分成划分成 不多于不多于 K 个等价类。个等价类。 Myhill Nerode （迈希尔（迈希尔-尼罗德）定理尼罗德）定理证明证明 3） 1）：）：L 确定的等价关系确定的等价关系 R
39、L 具有有穷指数具有有穷指数 |* / 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 |
40、 x L 令令 DFA 的状态转移函数：的状态转移函数：( x , a ) = xa ；其中，其中， x Q， a 如此构造的如此构造的 M 是接受是接受 L 的的 DFA。Myhill Nerode （迈希尔（迈希尔-尼罗德）定理尼罗德）定理1）RL 将将* 划分划分为有限为有限等价类算法：等价类算法： 给定接受正则语言给定接受正则语言 L 的的 DFA M ，用右不变等价关系，用右不变等价关系 RM 将将 * 划分为有限个划分为有限个 等价类，通过合并等价类，通过合并 set( qi ) ，求得语言，求得语言 L 确定确定 RL 划分划分 * 的有限等价类集合。的有限等价类集合。Myhil
41、l Nerode 定理的应用：定理的应用：2）证明一个语言）证明一个语言 L 不是不是 RL：RL 可将可将 * 划分为无穷个等价划分为无穷个等价类。类。Myhill Nerode （迈希尔（迈希尔-尼罗德）定理尼罗德）定理Myhill Nerode 定理定理例例8：对对 */RM = set (q0), set (q1), set (q2), set (q3), set (q4), set (q5) 中元素两两进中元素两两进行考察，通过合并行考察，通过合并 RM 等价类获得等价类获得 RL( M ) 的等价类集合，从而，求得最小自动机的等价类集合，从而，求得最小自动机。1、取取 00set
42、( 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、取取00set ( q0 ), 001set ( q2 ), 取取 z = 1* 有：00z L(M)， 001z L(M)。 所以所以, set( q0 ) 与与 set( q2 )不可合并为不可合并为 RL(M
43、) 同一等价类同一等价类同理，同理， 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 )， 所以，所以， 001z L( M ) 01z L( M ), set( q2 ), set( q3 ) 可合并。可合并。4、取取 1set ( q2 ), 10 set
44、 ( 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( M )，所以，所以，set( q2 ) 与与 set( q5 ) 不可合并。不可合并。设设 DFA M 接受语言：接受语言：
45、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 )*最小最小 DFA M：结果：等价关系结果：等价关系 RL(
46、M ) 划分划分 * 的字符串等价类：的字符串等价类：Myhill Nerode 定理定理推论推论 5-1： 对于任意的对于任意的 RL L，在同构意义下，接受，在同构意义下，接受 L 的极小的极小化化 DFA 是唯一的。是唯一的。Myhill Nerode （迈希尔（迈希尔-尼罗德）定理尼罗德）定理58自动机的极小化自动机的极小化问题的引出及极小化思路问题的引出及极小化思路最简自动机求解的相关概念最简自动机求解的相关概念Myhill Nerode （迈希尔（迈希尔-尼罗德）定理尼罗德）定理自动机极小化求解算法与求解实例自动机极小化求解算法与求解实例方法方法1：严格按照由严格按照由 RL 划分
47、划分 求求等价类的定义，从等价类的定义，从 set ( q ) 和和 set ( p ) 中各取一适当的字符串中各取一适当的字符串 x, y，利用右不变性质考察：对于任意，利用右不变性质考察：对于任意字符串字符串 z，x z 和和 y z 是否同时属于是否同时属于 L 和同时不属于和同时不属于 L。（如前例）。（如前例）评价：评价：1、需要对、需要对 M 中任意状态中任意状态 p、q 两两配对考察；两两配对考察；2、计算量与、计算量与M 中包含状态的个数中包含状态的个数 | Q | 以及所选字符串以及所选字符串 x, y, z 的长度的长度 有关，需要分析有关，需要分析 x, y, z 的结构
48、特征。的结构特征。存在两种合并方案：存在两种合并方案：自动机极小化求解算法自动机极小化求解算法算法的时间复杂度较高。算法的时间复杂度较高。方法方法2：1、不考虑哪些状态可以合并，反之，考虑哪些状态不能合并。、不考虑哪些状态可以合并，反之，考虑哪些状态不能合并。 - 找出所有不可合并状态，剩下的就是可合并状态；找出所有不可合并状态，剩下的就是可合并状态；自动机极小化求解算法自动机极小化求解算法存在两种合并方案：存在两种合并方案：2、考察从终态往始态方向进行搜索，确定任意两状态是否为不可合、考察从终态往始态方向进行搜索，确定任意两状态是否为不可合并状态。并状态。定义定义 57：设设 DFA M =
49、 ， 如果如果 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 和和
50、 q 也不能合并。也不能合并。自动机极小化算法：自动机极小化算法：输入：输入： 给定的给定的 DFA M = ；1） 对每个对每个 p F，q Q F 的状态对的状态对 ( q, p ) 加上可区分标记；加上可区分标记； /* 标记标记 p 和和 q 不可合并不可合并2） 对每个状态对对每个状态对 ( q, p ) F F ( Q - F ) ( Q - F ) 且且 q p，如果存在如果存在 a ，使得（，使得（(q, a), (p, a)）是一个已被标记为可区分状）是一个已被标记为可区分状态对，那么，对状态对态对，那么，对状态对 （q, p） 也加上可区分标记；也加上可区分标记；3）迭代执
