表明语言是无限的
Show a language is infinite
给定一个在字母表 ∑ 上定义了 n 个状态的 DFA M，以及一个满足 |x|>n 的字符串 x∈L(M)，我必须证明 L(M) 是一种无限语言。
有什么方法可以使用泵引理证明这一点吗？
我不是很确定为什么需要直接涉及抽取引理。证明思路与泵引理证明背后的思路相同，我们可以解释其中的关系。可能，有了这个解释，您可以想出一种方法来计算出直接依赖于泵引理的证明。我认为理论上应该可以在没有太多心理体操的情况下做到这一点。
想象一个具有三个状态的 DFA，它接受一个长度为 4 的字符串。这是要求您证明的一般声明的具体实例。如果我们能理解为什么这在这里特别正确，那么将更容易推广到具有任意数量状态的 DFA。
DFA 为输入的每个符号执行一个转换。每个转换都将 DFA 带到某个状态。由于接受了长度为 4 的字符串，我们执行了四个转换 - 从初始状态开始 - 我们最终处于某个接受状态。由于每次转换都将 DFA 带到某个状态，因此我们进入状态四次。由于 DFA 中只有三个状态，这意味着其中一个状态被转换为不止一次：我们不能在不访问某个状态超过一次的情况下围绕三个状态转换四次。这里的一般原理称为鸽洞原理：如果m个洞里有n只鸽子，且n>m，那么某个洞里有不止一只鸽子。顺便说一句，这与泵引理起作用的原因相同。
现在，考虑一下这个观察结果意味着什么。我们接受了一个字符串，并且在接受该字符串的同时，某些状态被访问了两次。这意味着在我们的 DFA 中某处有一个循环 - 一种从较晚状态进入较早状态的方法 - 而且，在进行循环后可以接受字符串。如果可以循环一次：
- 它可能根本没有被采用，所以 DFA 肯定接受了一个更短的字符串。
- 可能会被取两次，所以肯定有更长的字符串被DFA接受了。
- 事实上，它可能会被反复接受任意次数，因此语言中必须有无限多的更长的字符串。
在使用抽取引理时，您通常会假设一种语言是正则的，并得出抽取引理关于正则语言的说法——我们上面所说的——是正确的。然后，您提供一个反例 - 一个长度大于泵浦长度 p 的字符串（稍后会详细介绍 p 是什么） - 并得出假设是错误的，即语言不规则。
泵浦长度本质上是该语言的某些 DFA 中的状态数。如果语言是正则的，则有无限多的 DFA 接受它。出于使用泵引理的目的，您使用哪种语言的 DFA 并不重要，因为如果任何 DFA 处理长度超过 DFA 中状态数的输入，它都会多次访问某个状态。也许通常会为该语言想象一个最小的 DFA，它保证存在并且在同构之前是唯一的。
给定一个在字母表 ∑ 上定义了 n 个状态的 DFA M，以及一个满足 |x|>n 的字符串 x∈L(M)，我必须证明 L(M) 是一种无限语言。
有什么方法可以使用泵引理证明这一点吗？
我不是很确定为什么需要直接涉及抽取引理。证明思路与泵引理证明背后的思路相同，我们可以解释其中的关系。可能，有了这个解释，您可以想出一种方法来计算出直接依赖于泵引理的证明。我认为理论上应该可以在没有太多心理体操的情况下做到这一点。
想象一个具有三个状态的 DFA，它接受一个长度为 4 的字符串。这是要求您证明的一般声明的具体实例。如果我们能理解为什么这在这里特别正确，那么将更容易推广到具有任意数量状态的 DFA。
DFA 为输入的每个符号执行一个转换。每个转换都将 DFA 带到某个状态。由于接受了长度为 4 的字符串，我们执行了四个转换 - 从初始状态开始 - 我们最终处于某个接受状态。由于每次转换都将 DFA 带到某个状态，因此我们进入状态四次。由于 DFA 中只有三个状态，这意味着其中一个状态被转换为不止一次：我们不能在不访问某个状态超过一次的情况下围绕三个状态转换四次。这里的一般原理称为鸽洞原理：如果m个洞里有n只鸽子，且n>m，那么某个洞里有不止一只鸽子。顺便说一句，这与泵引理起作用的原因相同。
现在，考虑一下这个观察结果意味着什么。我们接受了一个字符串，并且在接受该字符串的同时，某些状态被访问了两次。这意味着在我们的 DFA 中某处有一个循环 - 一种从较晚状态进入较早状态的方法 - 而且，在进行循环后可以接受字符串。如果可以循环一次：
- 它可能根本没有被采用，所以 DFA 肯定接受了一个更短的字符串。
- 可能会被取两次，所以肯定有更长的字符串被DFA接受了。
- 事实上，它可能会被反复接受任意次数，因此语言中必须有无限多的更长的字符串。
在使用抽取引理时，您通常会假设一种语言是正则的，并得出抽取引理关于正则语言的说法——我们上面所说的——是正确的。然后，您提供一个反例 - 一个长度大于泵浦长度 p 的字符串（稍后会详细介绍 p 是什么） - 并得出假设是错误的，即语言不规则。
泵浦长度本质上是该语言的某些 DFA 中的状态数。如果语言是正则的，则有无限多的 DFA 接受它。出于使用泵引理的目的，您使用哪种语言的 DFA 并不重要，因为如果任何 DFA 处理长度超过 DFA 中状态数的输入，它都会多次访问某个状态。也许通常会为该语言想象一个最小的 DFA，它保证存在并且在同构之前是唯一的。