第4章正则语言的性质.ppt

1 第4章正则语言的性质 2 一 正则语言的封闭性质 定义4 1如果属于某一语言类的任何语言在某一特定运算下所得的结果仍然是该类语言 则称该语言类对此运算是封闭的 并称该语言类对此运算具有封闭性 closureproperty 给定正则语言L1和L2 它们的并集 交集 连接是否仍然是正则语言 定理4 1如果L1和L2是正则语言 那么L1 L2也是正则语言 证明 如果L1和L2是正则的 那么一定存在正则表达式r1和r2 使得L1 L r1 L2 L r2 根据定义 r1 r2是表示语言L1 L2的正则表达式 因此 正则语言对于并运算是封闭的 3 定理4 2如果L是字母表 上的正则语言 则L L是正则语言 证明 如果L是正则的 设接受L的DFA为M Q q0 F 下面构造DFAM 取M 与M的终结状态集互为补集 除了终结状态集为Q F外 M 的其余结构都与M相同 即M Q q0 Q F 显然 对于M接受的串 M 将不接受 对于M 接受的串 M将不接受 因此L M L所以 L是正则语言 4 例1设DFAM如图所示 它接受的语言为L w01 w 0 1 即接受所有以01结尾的0和1组成的串 用正则表达式的形式描述就是L M 0 1 01 L就是所有不以01结尾的由0和1组成的串 右图给出了 L M 的自动机 它把上图中的终结状态变为非终结状态 非终结状态变为终结状态 5 定理4 3如果L1和L2是正则语言 则L1 L2是正则语言 证明 用构造证明的方法 设L1 L M1 L2 L M2 其中DFAM1 Q1 1 q0 F1 DFAM2 Q2 2 p0 F2 构造DFAM Q1 Q2 F1 F2 其中 Q1 Q2 Q1 Q2对 p1 Q1 p2 Q2 a a 由定义可以看出 w被M接受当且仅当w同时被M1和M2接受 因此 L1 L2是正则的 6 例2设有如图下的两个DFA M1接受所有包含0的串 M2接受所有包含1的串 按定理4 3的构造方法 构造出的DFAM如右图所示 M接受的同时含有0和1的串 7 定理4 4如果L1和L2是正则语言 那么L1 L2也是正则语言 证明 根据集合差运算的定义有L1 L2 L1 L2 如果L1和L2是正则的 根据定理4 2 L2 是正则的 再由定理4 3 L1 L2 也是正则的 所以 正则语言在差运算上是封闭的 定理4 5如果L1和L2是正则语言 那么L1L2和L1 也都是正则语言 证明 如果L1和L2是正则的 那么一定存在正则表达式r1和r2 使得L1 L r1 L2 L r2 根据正则表达式的定义 r1r2和r1 分别是表示语言L1L2和L1 的正则表达式 因此 正则语言在连接和星闭包运算上都是封闭的 8 定理4 6如果L是正则语言 则L的逆LR w wT L wT表示w的倒序 也是正则语言 证明 证法1 用构造自动机的方法 假设L是正则语言 M是接受L的自动机 通过下面方法构造一个接受LR的自动机M 1 M 中的弧是M中所有弧的方向反转构成 2 M 的终结状态是M的初始状态 3 如果M不止一个终结状态 则在M 中创建一个新的初始状态 从该状态出发到M的所有终结状态都建立一个 转移 修改后的NFAM 接受wT 当且仅当M接受w 因此 M 接受LR 从而证明了逆运算的封闭性 9 证法2 设L由正则表达式r定义 对r的构造次数进行归纳证明 1 设r的构造次数为0 即r是 或者a 则 R R a R a 此时rR和r相同 2 设定理在r的构造次数小于k时成立 讨论r的构造次数等于k时 情况 设r r1 r2 其中r1和r2的构造次数都小于k 由归纳假设 可以构造r1R和r2R 使得L r1R L r1 R L r2R L r2 R 因为L r L r1 L r2 所以L r R L r1 R L r2 R 因此r1R r2R就是代表L r R的正则表达式 情况 设r r1r2 其中r1和r2的构造次数都小于k 由归纳假设 可以构造r1R和r2R 使得L r1R L r1 R L r2R L r2 R 由于L r L r1 L r2 因此L r R L r1 RL r2 R 所以r1Rr2R就是代表L r R的正则表达式 10 情况 设r r1 其中r1的构造次数小于k 由归纳假设 可以构造r1R 使得L r1R L r1 R 因为L r L r1 对于 w L r w w1w2 wm 每个wi L r1 wR wmRwm 1R w1R 其中每个wiR L r1 R 因此wR L r1R 反之 w L r1R w都有w1w2 wn的形式 其中wi L r1 R 因此 wR wnRwn 1R w1R L r1 L r 因此 r1R 就是代表L r R的正则表达式 11 例3设L是由正则表达式 0 1 0 表示的语言 根据连接规则可知LR是 0 R 0 1 R表示的语言 而 0 R 0 0或1的反转是它自身 即 0 1 R 0 1 因此LR的正则表达式为0 0 1 定义4 2假设 和 是两个字母表 函数h 如果对于 x y 都有h xy h x h y 则称h为 到 的同态映射 homomorphism 对于L h L h x 称为L的同态像 对于w h 1 w x h x w 称为w的同态原像 对于L h 1 L x h x L 称为L的同态原像 并称h 1 L 为L的逆同态 12 例4已知 0 1 和 a b c 定义h为h 0 abh 1 bcc那么h 010 abbccab L 00 010 的同态像为语言h L abab abbccab 例5已知 0 1 和 a b c 同态映射h为h 0 dbcch 1 bbc如果L是正则语言 使用正则表达式r 0 1 1 表示 那么r1 dbcc bbc bbc 表示的语言是正则语言h L 13 定理4 7如果L是字母表 上的正则语言 h是 到 上的同态映射 则h L 也是 上的正则语言 即正则语言在同态运算上是封闭的 证明 设L是用正则表达式r表示的正则语言 用h r 表示把r中的每个符号a 用h a 来代替后的表达式 根据正则表达式的定义 h r 也是正则表达式 下面证明h r 定义的语言是h L 即L h r h L r 对r的构造次数进行归纳 14 1 设r的构造次数为0 即r是 或者a 当r是 或者 时 L r 中或者只含空串 或者没有串 此时L h r L r 所以L h r h L r 当r是a时 L r a 所以h L r h a 另一方面 h r 是由符号串h a 表示的 上的正则表达式 因此L h r h a 所以L h r h L r 2 设定理在r的构造次数小于k时成立 讨论r的构造次数等于k时 设r r1 r2 其中r1和r2都是构造次数都小于k的正则表达式 由同态的定义 有h r h r1 r2 h r1 h r2 所以L h r L h r1 h r2 L h r1 L h r2 把h作用到一个语言上时 相当于把它单独作用到语言的每一个字符串 因此h L r h L r1 L r2 h L r1 h L r2 由归纳假设 L h r1 h L r1 L h r2 h L r2 所以 有L h r h L r 对于r r1r2 和r r1 可以类似地证明 15 定理4 8设h是字母表 到 上的同态映射 L是字母表 上的正则语言 则h 1 L 也是字母表 上正则语言 即正则语言在逆同态运算上是封闭的 证明略 定义4 3设L1和L2是定义在同一个字母表上的语言 我们称L1 L2 x xy L1对于某个y L2 为L1和L2的右商 rightquotient 由定义可以看出 L1和L2的右商中的符号串可以这样求出 先找出L1中所有其后缀属于L2的符号串 由每个这样的符号串去掉后缀后形成的符号串都属于L1 L2 16 例6设L1 anbm n 1 m 0 ba L2 bm m 1 L2中的符号串至少包含一个b 因此 先找出L1中其后缀为bt t 1 的串 这些串在 anbm n 1 m 1 中 将这些串去掉形为bt t 1 的后缀 得到L1 L2 anbm n 1 m 0 如果L1 L2是正则语言 L1 L2还是正则的吗 定理4 9如果L1和L2是正则语言 那么L1 L2也是正则语言 即正则语言在右商运算上是封闭的 证明 设M Q q0 F 是DFA 且L1 L M 构造一个DFAM Q q0 F 其中F qi qi Q且 y L2 使得 qi y F 17 下面证明L M L1 L2 由L1 L2的定义 对 x L1 L2 一定存在y L2 使得xy L1 即 q0 xy F因此 一定存在某个q Q 使得 q0 x q并且 q y F因此 根据构造可知q F 并且M 接受x 反之 对于M 接受的任意x 我们都有 q0 x q F 根据M 的构造 一定存在一个y L2 满足 q0 xy F 因此 xy属于L1 x属于L1 L2 得到L M L1 L2所以 L1 L2是正则的 18 例7已知L1 L a baa L2 L ab 求L1 L2 首先找到接受L1的DFA如图 19 定理4 9的方法构造DFAM Q q0 F 由于F qi qi Q且 y L2 使得 qi y F 从前图中可以看出 q1 q2 F 因此 接受L1 L2的自动机如下图 这个自动机接受由正则表达式a b a baa 表示的语言 将a b a baa 简化成a ba 因此L1 L2 L a ba 20 正则代换 regularsubstitution 设 是两个字母表 映射 被称为是从 到 的代换 如果对于 a f a 是 上的RL 则称f为正则代换 21 先将f的定义域扩展到 上 f f xa f x f a 再将f的定义域扩展到 对于 L 22 例8设 0 1 a b f 0 a f 1 b 则f 010 f 0 f 1 f 0 ab af 11 00 f 11 f 00 f 1 f 1 f 0 f 0 b b aa b aaf L 0 0 1 1 L a a b b L a a b b L a ab a b b L a b 23 f是正则代换 则 f f 对于 a f a 是 上的RE 如果r s是 上的RE 则f r s f r f s f rs f r f s f r f r 是 上的RE 24 定理4 10设L是 上的一个RL 是正则代换 则f L 也是RL 证明 描述工具 RE 对r中运算符的个数n施以归纳 证明f r 是表示f L 的RE 当n 0时 结论成立 当n k时定理成立 即当r中运算符的个数不大于k时 f L r L f r 25 当n k 1时 r r1 r2 f L f L r f L r1 r2 f L r1 L r2 RE的定义 f L r1 f L r2 正则代换的定义 L f r1 L f r2 归纳假设 L f r1 f r2 RE的定义 L f r1 r2 RE的正则代换的定义 L f r 26 r r1r2 f L f L r f L r1r2 f L r1 L r2 RE的定义 f L r1 f L r2 正则代换的定义 L f r1 L f r2 归纳假设 L f r1 f r2 RE的定义 L f r1r2 RE的正则代换的定义 L f r 27 r r1 f L f L r f L r1 f L r1 RE的定义 f L r1 正则代换的定义 L f r1 归纳假设 L f r1 RE的定义 L f r1 RE的正则代换的定义 L f r 28 例9设 0 1 2 a b 正则代换f定义为 f 0 ab f 1 b a f 2 a a b 则 f 00 abab f 010 abb a ab ab a b f 0 1 2 ab b a a a b b a a a b a b 29 二 RL的泵引理 泵引理 pumpinglemma 设L为一个RL 则存在仅依赖于L的正整数N 对于 z L 如果 z N 则存在u v w 满足 z uvw uv N v 1 对于任意的整数i 0 uviw L 30 证明思想 31 例1证明 0n1n n 1 不是RL 证明 假设L 0n1n n 1 是RLz 0N1N按照泵引理所述v 0kk 1此时有 u 0N k jw 0j1N 泵引理设L为一个RL 则存在仅依赖于L的正整数N 对于 z L 如果 z N 则存在u v w 满足 z uvw uv N v 1 对于任意的整数i 0 uviw L 32 从而有 uviw 0N k j 0k i0j1N 0N i 1 k1N当i 2时 我们有 uv2w 0N 2 1 k1N 0N k1N注意到k 1 所以 N k N 这就是说 0N k1N L这与泵引理矛盾 所以 L不是RL 泵引理设L为一个RL 则存在仅依赖于L的正整数N 对于 z L 如果 z N 则存在u v w 满足 z uvw uv N v 1 对于任意的整数i 0 uviw L 33 例2证明 0n n为素数 不是RL 证明 假设L 0n n为素数 是RL 取z 0N p L 不妨设v 0k k 1从而有 uviw 0N p k j 0k i0j 0N p i 1 k 泵引理设L为一个RL 则存在仅依赖于L的正整数N 对于 z L 如果 z N 则存在u v w 满足 z uvw uv N v 1 对于任意的整数i 0 uviw L 34 当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 注意到k 1 所以N p N p 1 1 k N p 1 k 不是素数 故当i N p 1时 uvN p 1w 0 N p 1 k L这与泵引理矛盾 所以 L不是RL 泵引理设L为一个RL 则存在仅依赖于L的正整数N 对于 z L 如果 z N 则存在u v w 满足 z uvw uv N v 1 对于任意的整数i 0 uviw L 35 例3证明 0n1m2n m m n 1 不是RL 证明 假设L 0n1m2n m m n 1 是RL 取z 0N1N22N设v 0kk 1从而有 uviw 0N k j 0k i0j1N22N 0N i 1 k1N22N 36 uv0w 0N 0 1 k1N22N 0N k1N22N注意到k 1 N k N 2N k 2N0N k1N22N L这个结论与泵引理矛盾 所以 L不是RL 37 用来证明一个语言不是RL不能用泵引理去证明一个语言是RL 由于泵引理给出的是RL的必要条件 所以 在用它证明一个语言不是RL时 我们使用反证法 泵引理说的是对RL都成立的条件 而我们是要用它证明给定语言不是RL 这就是说 相应语言的 仅仅依赖于L的正整数N 实际上是不存在的 因此 就用符号N来表示这个 假定存在 而实际并不存在的数 38 由于泵引理指出 如果L是RL 则对任意的z L 只要 z N 一定会存在u v w 使uviw L对所有的i成立 因此 我们在选择z时 就需要注意到论证时的简洁和方便 当一个特意被选来用作 发现矛盾 的z确定以后 就必须依照 uv N和 v 1的要求 说明v不存在 对 存在u v w 的否定 39 三 Myhill Nerode定理与DFA的极小化 对给定RLL DFAM接受L M不同 由RM确定的 上的等价类也可能不同 如果M是最小DFA 则M所给出的等价类的个数应该是最少的 最小DFA是不是惟一的 如果是 如何构造 最小DFA的状态对应的集合与其他DFA的状态对应的集合有什么样的关系 用这种关系是否能从一般的DFA出发 求出最小DFA 40 Myhill Nerode定理 定义 DFAM确定的等价关系 M Q q0 F 对于 x y xRMy q0 x q0 y 显然 xRMy q Q x y set q 41 例8设L 0 10 它对应的DFAM如下图 42 对应于q0 00 nRM 00 mn m 0 对应于q1 0 00 nRM0 00 mn m 0 对应于q2 00 n1RM 00 m1n m 0 对应于q3 0 00 n1RM0 00 m1n m 0 对应于q4 0 00 n10kRM0 00 m10hn m 0 k h 1 00 n10kRM 00 m10hn m 0 k h 1 0 00 n10kRM 00 m10hn m 0 k h 1 也就是 0n10kRM0m10hn m 0 k h 1 对应于q5 xRMy x y为至少含两个1的串 43 定义 L确定的 上的关系RL 对于 x y xRLy 对 z xz L yz L 对于 x y 如果xRLy 则在x和y后无论接 中的任何串z xz和yz要么都是L的句子 要么都不是L的句子 44 任意x y set q q0 x q0 y q对于 z q0 xz q0 x z q z q0 y z q0 yz 这就是说 q0 xz F q0 yz F 45 即 对于 z xz L yz L 表明 xRLy 也就是xRL M y 右不变的 rightlnvariant 等价关系设R是 上的等价关系 对于 x y 如果xRy 则必有xzRyz对于 z 成立 则称R是右不变的等价关系 46 命题1对于任意DFAM Q q0 F M所确定的 上的关系RM为右不变的等价关系 证明 RM是等价关系 自反性显然 对称性 x y xRMy q0 x q0 y 根据RM的定义 q0 y q0 x 的对称性 yRMx根据RM的定义 47 传递性 设xRMy yRMz 由于xRMy q0 x q0 y 由于yRMz q0 y q0 z 由 的传递性知 q0 x q0 z 再由RM的定义得 xRMz即RM是等价关系 48 RM是右不变的设xRMy 则 q0 x q0 y q所以 对于 z q0 xz q0 x z q z q0 y z q0 yz 这就是说 q0 xz q0 yz 再由RM的定义 xzRMyz所以 RM是右不变的等价关系 49 命题2对于任意L L所确定的 上的关系RL为右不变的等价关系 证明 RL是等价关系 自反性显然 对称性 不难看出 xRLy 对 z xz L yz L yRLx 50 传递性 设xRLy yRLz xRLy 对 w xw L yw L yRLz 对 w yw L zw L 所以 w xw L yw L且yw L zw L 即 对 w xw L zw L 故 xRLz即RL是等价关系 51 RL是右不变的 设xRLy 由RL的定义 对 w v xwv L ywv L 注意到v的任意性 知 xwRLyw 所以 RL是右不变的等价关系 指数 index 设R是 上的等价关系 则称 R 是R关于 的指数 简称为R的指数 简称 的关于R的一个等价类 也就是 R的任意一个元素 为R的一个等价类 52 例9下图所给DFAM所确定的RM的指数为6 RM将 分成6个等价类 set q0 00 n n 0 set q1 0 00 n n 0 set q2 00 n1 n 0 set q3 0 00 n1 n 0 set q4 0n10k n 0 k 1 set q5 x x为至少含两个1的串 53 RM是RL M 的 加细 refinement x y 如果xRMy 必有xRL M y成立 即对于任意DFAM Q q0 F RL M RM Q 按照RM中被分在同一等价类的串 在按照RL M 分类时 一定会被分在同一个等价类 RM对 的划分比RL M 对 的划分更 细 称RM是RL M 的 加细 refinement 54 RM set q0 set q1 set q2 set q3 set q4 set q5 取00 set q0 000 set q1 对于任意的x 当x含且只含一个1时 00 x L M 000 x L M 当x不含1或者含多个1时 00 x L M 000 x L M 这就是说 对于任意的x 00 x L M 000 x L M 即按照RL M 00与000被分在同一个等价类中 从而set q0 和set q1 被包含在RL M 的同一个等价类中 55 取00 set q0 001 set q2 取特殊的字符串1 001 L M 但0011 L M 所以 根据RL M set q0 和set q2 不能被 合并 到一个等价类中 类似地 根据RL M set q3 set q4 set q5 也都不能被 合并 到set q0 的句子所在的等价类中 56 取001 set q2 01 set q3 对于任意的x x要么不含1 要么含有1 当x不含1时 001x L M 01x L M 当x含有1时 001x L M 01x L M 这就是说 对于任意的x 001x L M 01x L M 即按照RL M 001与01属于RL M 的同一个等价类中 从而set q2 和set q3 被包含在RL M 的同一个等价类中 57 取1 set q2 10 set q4 对于任意的x x要么不含1 要么含有1 当x不含1时 1x L M 10 x L M 当x含有1时 1x L M 10 x L M 这就是说 对于任意的x 1x L M 10 x L M 即按照RL M 1与10被分在RL M 的同一个等价类中 从而在set q2 和set q4 被包含在RL M 的同一个等价类中 58 取1 set q2 11 set q5 注意到1 1 11 11 而1 L M 11 L M 即1和11不满足关系RL M 所以 set q2 和set q5 不能被 合并 到RL M 的同一个等价类中 在这里 是一个特殊的字符串 59 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 10 1 0 1 60 定理1 Myhill Nerode定理 如下三个命题等价 L 是RL L是 上的某一个具有有穷指数的右不变等价关系R的某些等价类的并 RL具有有穷指数 61 证明 由 1 可以推出 2 设L 是RL 所以 存在DFAM Q q0 F 使得L M L 由命题2 RM是 上的右不变等价关系 而且 RM Q 所以 RM具有有穷指数 而 L是 上的具有有穷指数的右不变等价关系RM的 对应于M的终止状态的等价类的并 62 由 2 可以推出 3 设xRy 由R的右不变性可知 对于任意z xzRyz而L是R的某些等价类的并 所以 xz L yz L根据RL的定义 xRLy故R是RL的加细 由于R具有有穷指数 所以 RL具有有穷指 63 由 3 可以推出 1 令M RL x x L 表示 所在的等价类对应的状态 x 表示x所在的等价类对应的状态 对于 x a RL x a xa 定义的相容性L M L 64 例10用定理1证明 0n1n n 0 不是RL根据L的句子的特征来寻找RL的等价类 L的句子的主要特点有两个 句子中所含的字符0的个数与所含的字符1的个数相同 所有的0都在所有的1的前面可以得到如下一些等价类 65 10 x x 0n1m m n 1 或者x中含子串10 所在的等价类 1 0所在的等价类 2 00所在的等价类 3 000所在的等价类 n 0n所在的等价类 所以 RL的指数是无穷的 因此 L不是RL 66 推论1对于任意的RLL 如果DFAM Q q0 F 满足L M L 则 RL Q 表明 对于任意DFAM Q q0 F Q RL M 也表明 对任意一个RLL 按照定理中所给的方法构造出来的DFAM 是一个接受L的最小DFA 这个DFA是惟一的么 67 推论2对于任意的RLL 在同构意义下 接受L的最小DFA是惟一的 证明 接受L的最小DFAM Q q0 F 的状态数与RL的指数相同 也就是说 这个最小DFA的状态数与Myhill Nerode定理证明中构造的M RL x x L 的状态数是相同的 68 DFA同构是指这两个DFA的状态之间有一个一一对应 而且这个一一对应还保持状态转移也是相应一一对应的 也就是说 如果q与 w 对应 p与 z 对应 当 q a p时 必定有 w a z 这两个DFA是同构 定义映射ff q f q0 x x x q0 x q 69 f为Q与 RL之间的一一对应如果 q0 x q0 y 则xRMy由于RM是RL的加细 所以 xRLy故 x y 即 x y 如果 q0 x q0 y 则 x y 即 x y 否则 RM RL 70 如果 q a p f q x 必有f p xa q Q 如果 f q f q0 x x 所以 a 如果 p q a q0 x a q0 xa 则f p f q a f q0 x a f q0 xa xa 即 如果M在状态q读入字符a时进入状态p 则M在q对应的状态f q0 x x 读入字符a时 进入p对应的状态f q0 xa xa 所以 f是M和M 之间的同构映射 71 DFA的极小化 可以区分的 distinguishable 状态设DFAM Q q0 F 如果 x 对Q中的两个状态q和p 使得 q x F和 p x F中 有且仅有一个成立 则称p和q是可以区分的 否则 称q和p等价 并记作q p 72 算法1DFA的极小化算法算法思想 扫描所有的状态对 找出所有的可区分的状态对 不可取分的状态对一定是等价的 输入 给定的DFA 输出 可区分状态表 主要数据结构 状态对的关联链表 可区分状态表 73 主要步骤 for q p F Q F do标记可区分状态表中的表项 q p for q p F F Q F Q F q pdo if a 可区分状态表中的表项 q a p a 已被标记thenbegin 标记可区分状态表中的表项 q p 递归地标记本次被标记的状态对的关联链表上的各个状态对在可区分状态表中的对应表项end 74 elsefor a do if q a p a q p 与 q a p a 不是同一个状态对then将 q p 放在 q a p a 的关联链表上 75 定理2对于任意DFAM Q q0 F Q中的两个状态q和p是可区分的充要条件是 q p 在DFA的极小化算法中被标记 证明 先证必要性 设q和p是可区分的 x是区分q和p的最短字符串 现施归纳于x的长度 证明 q p 一定被算法标记 76 当 x 0时 区分q和p 表明q和p有且仅有一个为M的终止状态 所以 q p F Q F 因此 它在算法的第 1 行被标记 设当 x n时结论成立x是区分q和p的长度为n的字符串 则 q p 被算法标记 77 当 x n 1时设x ay 其中 y n 由于x是区分q和p的最短的字符串 所以 q x F和 p x F中 有且仅有一个成立 不妨假设 q x F p x F即 q a y F p a y F设 q a u p a vy是区分u和v的长度为n的字符串 78 由归纳假设 u v 可以被算法标记 如果在考察 q p 时 u v 已经被标记 则 q p 在算法的第 4 行被标记 如果在考察 q p 时 u v 还没有被标记 则 q p 在算法的第 7 行被放入到 u v 的关联链表中 而当 u v 被标记时 在算法的第 5 行在 递归 过程中 q p 被标记 结论对 x n 1成立 79 充分性 设 q p 在算法中被标记 对它被标记的顺序n施归纳 证明q和p是可区分的 令 F Q F m 显然 当1 n m时 q p 是在算法的第 1 行被标记的 此时 是区分q和p的字符串 q F和 p F有且仅有一个成立 80 设n k k m 时结论成立 即 如果 q p 是被算法在第k个或者第k个之前标记的 则存在字符串x x区分q和p 即 q x F和 p x F有且仅有一个成立 当n k 1时 如果 q p 是在算法的第 4 行被标记的 此时 q a p a 一定是在第k个之前被标记的 设 q a u p a v 由归纳假设 存在字符串x x区分u和v u x F和 v x F有且仅有一个成立 从而 q ax F和 p ax F有且仅有一个成立 即 ax是区分q和p的字符串 81 如果 q p 是在算法的第 5 行被标记的 则它必在某个状态对 u v 的关联链表中 而 u v 必在 q p 之前被标记 由归纳假设 存在x区分 u v 存在a q a u p a v使得 q p 被放在 u v 的关联链表中 ax是区分q和p的字符串 所以 结论对n k 1成立 由归纳法原理 结论对所有的n成立 82 定理3由算法1构造的DFA在去掉不可达状态是最小DFA 证明 设M Q q0 F 为算法5 1的输入DF