如何用泵引理证明：含n个状态的DFA接受长于n的串则语言无限？

这其实是泵引理最经典的应用场景之一——用它推导正则语言的无限性。咱们一步步理清楚逻辑：

首先明确正则语言泵引理的核心内容（针对n状态DFA的情况，泵长度p ≤ n）：

若L是正则语言（即被某个DFA接受的语言），则存在一个常数p，对于任意s ∈ L且|s| ≥ p，都能把s拆分成xyz三个部分，满足：

1. |y| ≥ 1（y不是空串）
2. |xy| ≤ p（y的位置在前p个字符范围内）
3. 对所有非负整数k，xyᵏz都属于L

回到你的问题：已知存在x ∈ L(M)且|x| > n，而DFA的泵长度p最多等于它的状态数n，所以|x| ≥ p完全满足泵引理的应用前提。

接下来是关键推导：

• 根据泵引理，x可以拆分为xyz，其中y的长度至少为1。
• 我们可以构造一系列字符串：xy⁰z（即xz，长度比x短|y|）、xy¹z（就是x本身）、xy²z（长度比x长|y|）、xy³z（再长|y|）……
• 这些字符串的长度各不相同，且根据泵引理第三条，每一个都属于L(M)。

既然L(M)包含无穷多个长度不同的字符串，那它必然是无限语言。

补充个小背景：这个证明本质是鸽巢原理的延伸——当在DFA中走超过n步（n为状态数），必然会重复经过某个状态，形成可循环的“环”，泵引理里的y就是这个环对应的字符串，重复循环这个环就能得到无限多合法串，这也是泵引理能证明无限性的核心原因。

内容的提问来源于stack exchange，提问作者CXB