计算机数学基础第三章.pptVIP

第三章 正规集的性质 正规集的泵作用引理 如果一个语言是正规的，则它被一个具有某一具体数目的状态n的确定的有限自动机M= (Q, ?, ?, q0, F)所接受。 引理3.1（Pumping Lemma)：设L为正规集，则存在一个常数n，使得若L中有字Z，而|Z| ≥ n，则Z可写为Z = uvw，使得|uv| ≤ n，|v| ≥1，并对所有的i ≥0，uviw仍然在L中。更进一步说，n不大于接受L的最小的有限自动机的状态数。 泵作用引理的应用 泵作用引理用于证明某些集合不是正规集时，应用的一般方式是采用如下形式的反证法： (1) 假定你想要证明的语言L是正规的。 (2) 确定泵作用引理中的常数n，n一旦确定，则不可改变。 (3) 挑选L中句子Z，Z的选择隐含地依赖于n 的值。 (4) 在满足|uv| ≤ n和|v| ≥ 1的约束条件下，将Z分成u，v和w。 (5) 通过证明对?u ,v和w，存在i，使得uviw ? L，从而得出矛盾。由此断定L不是正规的。 泵作用引理的应用 例3.1：集合L = {0k| k = i2，这里i是整数，且i ? 1}，即L是由长度为完全平方的0的符号串构成的集合。L不是正规的。 证明：假定L是正规的并设n为泵作用引理中的常数。令Z = 0n2。由泵作用引理，z = uvw，其中1? |v|? n，并且对所有的i，uviw都在L中。然而，若取i = 2，则n2 | uv2w | ≤ n2 + n (n + 1)2，也就是说，uv2w的长度恰好位于n2和(n+1)2之间。从而不是一个完全平方。因此uv2w?L。与泵作用引理矛盾，故L不是正规的。 二进制素数的集合不是正规集 例3.2：令L是这样一些0和1的符号串的集合，这些符号串以1开头，将它们看成二进制数时它们的值是素数。即L是所有二进制素数构成的集合。 证明：假定L是正规的并设常数为n。 令Z是的二进制素数p，p 2n。因为有无穷多的素数，所以素数p存在。由泵作用引理，Z = uvw，其中|v| ≥ 1，并对?i，uviw仍然是二进制素数。将符号串u、v和w作为二进制数的值记为nu，nv，和nw。若u或w为ε，则令nu或nw为0。 二进制素数的集合不是正规集 从而有S ≡ 1(mod p)。于是 正规集的封闭性质 正规集对并，联结和kleene闭包是封闭的。 正规集合类对补运算封闭。 正规集对交运算封闭。 正规集对所有的布尔运算封闭。 正规集合类对正规替换是封闭的。 正规集合类对同态和逆同态都是封闭的。 正规集合类对与任何集合的商是封闭的 正规集对交运算封闭。 定理3.3：正规集对交运算封闭。 证明：由德摩根律，有 即两个集合的交集可以定义为它们的补集之并的补集。因此，可由正规集对并运算和补运算的封闭性质直接得出正规集对交运算封闭性质。 正规集对交运算封闭。 定理3.3：正规集对交运算封闭。 证明：设M1 = (Q1, ?, ?1, q1, F1)和M2 = (Q2, ?, ?2, q2, F2)为两个确定的有限自动机。 构造M = (Q1×Q2, ?, [q1, q2], F1×F2)，其中?定义为：对所有p1 ? Q1，p2 ? Q2和a ? ?， ?([p1, p2], a)=[?1(p1, a), ?2(p2, a)]。 容易证明L(M) = L(M1) ? L(M2)。 双向相乘的结果相等的集合 例3.3：构造有限自动机接受字母表{a，b，c}上所有按右图的乘法表从左往右相乘和从右往左相乘的值相等的符号串的集合。 双向相乘的结果相等的集合 现在考虑(2)：执行从右往左相乘的运算。 可不可以用一个自动机从右向左扫描输入来完成该运算呢？ 不可以！因为这样需要一个缓冲区来存放输入，这不是用有限状态可以实现的。 我们必须在从左至右扫描的过程实现从右向左的运算，在扫描结束后知道其结果。怎么做？ 猜测。猜测从右向左运算的结果是a，是b，或者是c。然后从左至右检测哪个猜测是正确的。 除法 先来看两个符号的情形，设猜测的结果为R，扫描的符号依次是X和Y，若满足Y*X = R，则此猜测是正确的。 换言之，若Y = R/X，则结果为R是正确的，否则是错误的。 对于多个符号相乘的情形，也不难按同样的方法依次地逐个进行检测。 因此，这里需要实现的是乘法的逆运算，除法。 除法 由乘法表可以得到对应的除法表： 让左乘和右乘同时进行 用ML、Ma、Mb和Mc来共同构造有限自动机M。 四个自动机同时工作：ML计算左乘的结果，Ma、Mb和Mc同时猜测右乘的结果。如果ML的结果与它们中某个猜测的结果相同，则说明该符号串左乘和右乘的结果一样。该符号串就