显示语言是无限的

我不能立即确定为什么需要直接涉及泵引理。证明思路与泵引理的证明思路相同,我们可以解释这种关系。也许,有了这个解释,你可以找到一种方法,直接依靠泵引理来证明。我认为从理论上讲,不需要太多的心理训练就可以做到这一点。

假设一个具有三个状态的DFA接受长度为四的字符串。这是你被要求证明的一般主张的一个具体例子。如果我们能够理解为什么这里的情况是这样的,那么将更容易推广到具有任意数量状态的DFA。

DFA对每个输入符号执行一次转换。每个转换都将DFA带到某个状态。由于长度为4的字符串被接受,我们从初始状态开始执行四个转换,最后进入某种接受状态。由于每次转换都会将DFA带到某个状态,因此我们会四次进入状态。由于DFA中只有三个州,这意味着其中一个州被过渡到了不止一次:如果不多次访问某个州,我们就不能围绕三个州进行四次过渡。这里的一般原则被称为鸽子洞原则:如果m洞中有n只鸽子,则n>m、 然后某个洞里有不止一只鸽子。顺便说一句,这也是为什么泵引理起作用的原因。

现在,考虑一下这个观察结果意味着什么。我们接受了一个字符串,在接受该字符串的同时,访问了两次某个州。这意味着在我们的DFA中某处有一个循环-一种从后一个状态到早期状态的方法-而且,在进行循环后,可以接受字符串。如果循环可以进行一次:

• 它可能根本没有被接受,所以DFA肯定会接受一个较短的字符串。
• 它可能需要两次,因此DFA肯定会接受更长的字符串。
• 事实上,它可能被重复任意次数,因此语言中必须有无限多个更长的字符串。

当使用泵引理时,通常假设一种语言是正则的,并得出结论,泵引理所说的关于正则语言的内容——我们上面所说的内容——是真的。然后,您提供了一个反例-一个长度大于泵送长度p的字符串(更多地是关于p在某一时刻的值),并得出结论,该假设是错误的,即语言是不规则的。

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