infinite - 显示语言是无限的

Question

给定一个在字母 ∑ 上定义了 n 个状态的 DFA M，以及一个满足 |x|>n 的字符串 x∈L(M)，我必须证明 L(M) 是一种无限语言。

有什么方法可以使用抽水引理证明这一点？

Answer 1

我不确定为什么需要直接涉及抽水引理。证明思想与抽水引理证明背后的思想相同，我们可以解释这种关系。可能，有了这个解释，您可以找到一种方法来计算出直接依赖于抽水引理的证明。我认为理论上应该可以在没有太多心理体操的情况下做到这一点。

想象一个具有三个状态的 DFA，它接受长度为 4 的字符串。这是您被要求证明的一般主张的具体实例。如果我们能理解为什么这里特别正确，那么将更容易推广到具有任意数量状态的 DFA。

DFA 为每个输入符号执行一次转换。每个转换都将 DFA 带到某个状态。由于长度为 4 的字符串被接受，我们执行了四个转换——从初始状态开始——我们最终处于某种接受状态。由于每次转换都将 DFA 带到某个状态，因此我们四次进入状态。由于 DFA 中只有三个状态，这意味着其中一个状态被转换到不止一次：我们不能在不多次访问某个状态的情况下围绕三个状态转换四次。这里的一般原则被称为鸽巢原则：如果 m 个洞中有 n 只鸽子，并且 n > m，那么某个洞有不止一只鸽子。顺便说一句，这与抽水引理起作用的原因相同。

现在，考虑一下这个观察意味着什么。我们接受了一个字符串，并且在接受该字符串时，某个状态被访问了两次。这意味着在我们的 DFA 中某处存在一个循环——一种从较晚状态进入较早状态的方法——此外，可以在执行循环后接受字符串。如果循环可以执行一次：

• 它可能根本没有被采用，因此 DFA 肯定接受了一个较短的字符串。
• 它可能需要两次，因此 DFA 肯定接受更长的字符串。
• 事实上，它可能会被多次接管，因此语言中必须有无限多的更长的字符串。

在使用抽引引理时，您通常假设一种语言是规则的，并得出结论，抽引引理对常规语言的描述——我们在上面所说的——是正确的。然后，您提供一个反例 - 一个长度大于泵送长度 p 的字符串（更多关于 p 的内容） - 并得出假设是错误的，即语言不规则。

泵送长度本质上是该语言的某些 DFA 中的状态数。如果语言是正则的，那么接受它的 DFA 将是无限多的。出于使用泵引理的目的，您使用哪种语言的 DFA 并不重要，因为如果任何 DFA 处理长度超过 DFA 中状态数的输入，它都会多次访问某个状态。也许通常为语言想象一个最小的 DFA，它保证存在并且在同构之前是唯一的。