## Beginner ### 1. $\{0^n1^n| n \geq 0\}$ 1. Suppose $L$ is regular 2. Exists a "pumping constant" $p$ for $L$ **重点技巧：不管你这个 $p$ 是啥，直接 substitute 到 n 上。也就是变成 $0^p1^p$** 3. Choose a string $w = 0^p1^p$ 4. **重点技巧：然后找一个拆分这个 string 变成 $xyz$ 的方式**，满足（本来是有三个条件的，但是你最后一个条件是用来引起反例的，因此这里只需要考虑前两个条件） 1. $|xy| \leq p$ 2. $|y| \geq 1$ 这里的话，假设：$x = 0^{\alpha}, y = 0^{\beta}$, 其中 $a \geq 0, \beta \geq 1$ 因为上面的条件2要求了 $|y| \geq 1$，然后当然满足：$\alpha + \beta = p$。这样的话有：$z = 0^{p - (\alpha + \beta) 1^p}$ 现在要满足 Pumping Lemma，写出来 $xy^iz = 0^{\alpha}0^{\beta}0^{p - (\alpha + \beta) }1^p = 0^{p + (i-1)\beta}1^p$ 然后要让当前构造的 $w \not\in L$ 的话， 只要是 $p + (i - 1)\beta \not = p$ 即可，推出来 $i \neq 1$。那么简单选一个 $i = 2$ 就可以让 $w \not\in L$。 因此，$L$ 不是 regular language。 ### 2. $\{w \in \{0,1\}^*|w \text{ has the same number of 0's and 1's}\}$ #### 法一 因为 regex 在 intersection 是 close 的，所以因为 $\{0^n1^n| n \geq 0\}$ 是 regular 的而其又属于当前这个 language，所以当前 language 是 regular 的。 #### 法二 说白了，其实可以假设一个长度为 $p$ 的排列，使得所有为 $0$ 的位置都在前面，为 $1$ 的位置都在后面。因为这样的排列一定存在，所以该langauge自然退化到$\{0^n1^n| n \geq 0\}$ 这个langauge 的情形。 ### 3. $\{w \in \{0,1\}^*|w \text{ has the more number of 1's than 1's}\}$ 还是按照 2. 的法二，因为我们存在一个排列重排 $0,1$ 的顺序，那么我们只要证明 $L' = \{0^n1^{n+1}| n \geq 0\}$ 不是 regular 就行了。这里简单地取 $n + 1$ 就可以保证 1 比 0 多了嘛。 然后还是 1. 的过程，最后是得到了 $\beta(i-1) < 1 \Leftrightarrow (i-1) < \frac{1}{\beta} $ ，因为 $i \in \mathbb{N} \land i \geq 0$ 又有 $\beta \geq 1$，所以 $i = 2$。套进去效果类似。不写了。 ### 4. $\{0^{2n} 1^n | n \geq 0\}$ 类似于 1. ，如果按照 1 的分解最后是 $i \not = 1$，选个 $i = 2$ 即可。 ### 5. $\{0^{n}1 0^n | n \geq 0\}$ 类似于 1. ，如果按照 1 的分解最后是 $i \not = 1$，选个 $i = 2$ 即可。 ### 总结1：对于 $\{0^m1^n0^{f(m, n)} | m, n \geq 0 \}$ 以上所有都可以泛化成该形式，比如可以定义: $f(m, n) = m + n$ 或者 $f(m, n) = m \times n $。 对于不钦定顺序的，可以直接给一个排列 $p$ 使其有序，然后令 $f(m, n) = 0$ 即可（当然也可以是别的常数） ### 6. $\{0^n1^m| n \neq m\}$ **重点技巧：p! 方法** (相当于不管我们要配多少使得 $n = m$，这个差值（体现在指数上就是加减法了）都被阶乘包含了) 选择：$w = 0^{p}1^{p + p!}$ 令：$x = 0^{\alpha}, y = 0^{\beta}, z = 0^{p - \alpha - \beta}1^{p + p!}$，**其中注意：$\beta \in [0, p]$** 那么写成：$xy^iz$ 发现 $(i - 1) \beta \neq p!$ ，然后因为 $\beta | p!$ ，所以 $i \neq \frac{p!}{\beta} + 1$，那么选择这个 $i = \frac{p!}{\beta} + 1$ 即可。 ### 7. $\{0^n1^m | n < 3m\}$ 不写了，唯一需要注意的是 $|xy| \leq p$ ## Regular ### 8. $\{0^{n^2} | n \geq 0\}$ 取 $t$ 使 $2t+1>p$（例如直接取 $t=p$）。令 $$ w=0^{t^2}\in L. $$ 对 **任意** 分解 $w=xyz$ 且 $|xy|\le p,\ |y|>0$，因为全是 0，所以设 $y=0^k$，其中 $1\le k\le p$。 考虑泵一次：$i=2$。此时 $$ |xy^2z|=t^2+k. $$ 又因为 $1\le k\le p<2t+1$，所以 $$ t^2< t^2+k \le t^2+p < t^2+(2t+1)=(t+1)^2. $$ 因此 $|xy^2z|$ 的长度严格处在两个相邻平方数 $t^2$ 与 $(t+1)^2$ 之间，不可能是完全平方数，故 $xy^2z\notin L$。这与泵引理“对所有 $i\ge 0$ 仍在 $L$”矛盾。于是 $L$ 非正则，证毕。 （同理也可取 $i=0$ 得到 $t^2-k$ 落在 $(t-1)^2$ 与 $t^2$ 之间，依然不为平方数。） ### 9. Power of 2 例如：$\{0^{2^n} | n \geq 0\}$ 设 Pumping Length $p$，选择 $w = 0^{2^p}$。 令 $x = 0^{\alpha}, y = 0^{\beta}, z = \text{rest}$ 若 $xy^iz \in L$ ，$xy^iz = 0^{\alpha}0^{i\beta}0^{2^p - \alpha - \beta} = 0^{2p + (i - 1)\beta}$， 则：$2^{p} + (i - 1)\beta$ 是 2 的幂 令 $i = 2$ ，则 $2^p <2^p + \beta \leq 2^p + p < 2^{p} + 2^{p} = 2^{p+1}$ ，因为 $\beta \geq 1 \land \beta \leq p$ ### 10. Primes 例如：$\{0^k | k \text{ is a prime}\}$ 假设我们有 $w = 0^{r}$，**r 是 pumping lenth p 的 $p+2$ 的下一个质数** 拆分 $xy^iz \not\in L$，有： $|xy^iz| = |xz| + i|y|$ ，想要的形式是：$(|y| + 1)|xz|$ 当 $i = |xz|$ 的时候取到。 这样一来因为 $|xy| \leq p, |w| \geq p + 2 \Rightarrow |z| \geq 2$ ，所以 $|xz| \geq 2$。 又有 $(|y| + 1) \geq 2 $，所以这必然是一个合数。 ### 11. $\{0^m1^n | \frac{m}{n} \text{is an interger}\}$ 选择 $w = 0^{4p}1^{2p}$ 最后分出来条件是：$\frac{4p + (i - 1)\beta}{2p}$ ， 选一个 $i = 2$ ，那么 $\beta = 2p$ 才行。但是 $\beta \in [1, p]$ ### 12. $\{w \in \{0, 1\}^{*} | \text{00 or 11 appear same \# of times in w}\}$ 懒得写了 ### 13. $\{w \in \{0,1\}^* | w \text{ is not a palindrome}\}$ 选择 $w = 0^p110^{p + p!}$ $x = 0^{\alpha}, y = 0^{\beta}, z = 0^{p - \alpha - \beta}110^{p+ p !}$ 所以有 $xy^iz = 0^{p + (i - 1)\beta}110^{p + p !}$ 然后就是套路了 Loading... ## Beginner ### 1. $\{0^n1^n| n \geq 0\}$ 1. Suppose $L$ is regular 2. Exists a "pumping constant" $p$ for $L$ **重点技巧：不管你这个 $p$ 是啥，直接 substitute 到 n 上。也就是变成 $0^p1^p$** 3. Choose a string $w = 0^p1^p$ 4. **重点技巧：然后找一个拆分这个 string 变成 $xyz$ 的方式**，满足（本来是有三个条件的，但是你最后一个条件是用来引起反例的，因此这里只需要考虑前两个条件） 1. $|xy| \leq p$ 2. $|y| \geq 1$ 这里的话，假设：$x = 0^{\alpha}, y = 0^{\beta}$, 其中 $a \geq 0, \beta \geq 1$ 因为上面的条件2要求了 $|y| \geq 1$，然后当然满足：$\alpha + \beta = p$。这样的话有：$z = 0^{p - (\alpha + \beta) 1^p}$ 现在要满足 Pumping Lemma，写出来 $xy^iz = 0^{\alpha}0^{\beta}0^{p - (\alpha + \beta) }1^p = 0^{p + (i-1)\beta}1^p$ 然后要让当前构造的 $w \not\in L$ 的话， 只要是 $p + (i - 1)\beta \not = p$ 即可，推出来 $i \neq 1$。那么简单选一个 $i = 2$ 就可以让 $w \not\in L$。 因此，$L$ 不是 regular language。 ### 2. $\{w \in \{0,1\}^*|w \text{ has the same number of 0's and 1's}\}$ #### 法一 因为 regex 在 intersection 是 close 的，所以因为 $\{0^n1^n| n \geq 0\}$ 是 regular 的而其又属于当前这个 language，所以当前 language 是 regular 的。 #### 法二 说白了，其实可以假设一个长度为 $p$ 的排列，使得所有为 $0$ 的位置都在前面，为 $1$ 的位置都在后面。因为这样的排列一定存在，所以该langauge自然退化到$\{0^n1^n| n \geq 0\}$ 这个langauge 的情形。 ### 3. $\{w \in \{0,1\}^*|w \text{ has the more number of 1's than 1's}\}$ 还是按照 2. 的法二，因为我们存在一个排列重排 $0,1$ 的顺序，那么我们只要证明 $L' = \{0^n1^{n+1}| n \geq 0\}$ 不是 regular 就行了。这里简单地取 $n + 1$ 就可以保证 1 比 0 多了嘛。 然后还是 1. 的过程，最后是得到了 $\beta(i-1) < 1 \Leftrightarrow (i-1) < \frac{1}{\beta} $ ，因为 $i \in \mathbb{N} \land i \geq 0$ 又有 $\beta \geq 1$，所以 $i = 2$。套进去效果类似。不写了。 ### 4. $\{0^{2n} 1^n | n \geq 0\}$ 类似于 1. ，如果按照 1 的分解最后是 $i \not = 1$，选个 $i = 2$ 即可。 ### 5. $\{0^{n}1 0^n | n \geq 0\}$ 类似于 1. ，如果按照 1 的分解最后是 $i \not = 1$，选个 $i = 2$ 即可。 ### 总结1：对于 $\{0^m1^n0^{f(m, n)} | m, n \geq 0 \}$ 以上所有都可以泛化成该形式，比如可以定义: $f(m, n) = m + n$ 或者 $f(m, n) = m \times n $。 对于不钦定顺序的，可以直接给一个排列 $p$ 使其有序，然后令 $f(m, n) = 0$ 即可（当然也可以是别的常数） ### 6. $\{0^n1^m| n \neq m\}$ **重点技巧：p! 方法** (相当于不管我们要配多少使得 $n = m$，这个差值（体现在指数上就是加减法了）都被阶乘包含了) 选择：$w = 0^{p}1^{p + p!}$ 令：$x = 0^{\alpha}, y = 0^{\beta}, z = 0^{p - \alpha - \beta}1^{p + p!}$，**其中注意：$\beta \in [0, p]$** 那么写成：$xy^iz$ 发现 $(i - 1) \beta \neq p!$ ，然后因为 $\beta | p!$ ，所以 $i \neq \frac{p!}{\beta} + 1$，那么选择这个 $i = \frac{p!}{\beta} + 1$ 即可。 ### 7. $\{0^n1^m | n < 3m\}$ 不写了，唯一需要注意的是 $|xy| \leq p$ ## Regular ### 8. $\{0^{n^2} | n \geq 0\}$ 取 $t$ 使 $2t+1>p$（例如直接取 $t=p$）。令 $$ w=0^{t^2}\in L. $$ 对 **任意** 分解 $w=xyz$ 且 $|xy|\le p,\ |y|>0$，因为全是 0，所以设 $y=0^k$，其中 $1\le k\le p$。 考虑泵一次：$i=2$。此时 $$ |xy^2z|=t^2+k. $$ 又因为 $1\le k\le p<2t+1$，所以 $$ t^2< t^2+k \le t^2+p < t^2+(2t+1)=(t+1)^2. $$ 因此 $|xy^2z|$ 的长度严格处在两个相邻平方数 $t^2$ 与 $(t+1)^2$ 之间，不可能是完全平方数，故 $xy^2z\notin L$。这与泵引理“对所有 $i\ge 0$ 仍在 $L$”矛盾。于是 $L$ 非正则，证毕。 （同理也可取 $i=0$ 得到 $t^2-k$ 落在 $(t-1)^2$ 与 $t^2$ 之间，依然不为平方数。） ### 9. Power of 2 例如：$\{0^{2^n} | n \geq 0\}$ 设 Pumping Length $p$，选择 $w = 0^{2^p}$。 令 $x = 0^{\alpha}, y = 0^{\beta}, z = \text{rest}$ 若 $xy^iz \in L$ ，$xy^iz = 0^{\alpha}0^{i\beta}0^{2^p - \alpha - \beta} = 0^{2p + (i - 1)\beta}$， 则：$2^{p} + (i - 1)\beta$ 是 2 的幂 令 $i = 2$ ，则 $2^p <2^p + \beta \leq 2^p + p < 2^{p} + 2^{p} = 2^{p+1}$ ，因为 $\beta \geq 1 \land \beta \leq p$ ### 10. Primes 例如：$\{0^k | k \text{ is a prime}\}$ 假设我们有 $w = 0^{r}$，**r 是 pumping lenth p 的 $p+2$ 的下一个质数** 拆分 $xy^iz \not\in L$，有： $|xy^iz| = |xz| + i|y|$ ，想要的形式是：$(|y| + 1)|xz|$ 当 $i = |xz|$ 的时候取到。 这样一来因为 $|xy| \leq p, |w| \geq p + 2 \Rightarrow |z| \geq 2$ ，所以 $|xz| \geq 2$。 又有 $(|y| + 1) \geq 2 $，所以这必然是一个合数。 ### 11. $\{0^m1^n | \frac{m}{n} \text{is an interger}\}$ 选择 $w = 0^{4p}1^{2p}$ 最后分出来条件是：$\frac{4p + (i - 1)\beta}{2p}$ ， 选一个 $i = 2$ ，那么 $\beta = 2p$ 才行。但是 $\beta \in [1, p]$ ### 12. $\{w \in \{0, 1\}^{*} | \text{00 or 11 appear same \# of times in w}\}$ 懒得写了 ### 13. $\{w \in \{0,1\}^* | w \text{ is not a palindrome}\}$ 选择 $w = 0^p110^{p + p!}$ $x = 0^{\alpha}, y = 0^{\beta}, z = 0^{p - \alpha - \beta}110^{p+ p !}$ 所以有 $xy^iz = 0^{p + (i - 1)\beta}110^{p + p !}$ 然后就是套路了 最后修改：2025 年 11 月 08 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 1 如果觉得我的文章对你有用，请随意赞赏
1 条评论
手艺匪浅