这是证明一种语言不是正则语言的引理：如果 L 是正则语言，则存在一个 const N 使得对于 L 中的每个 z，|z|>=N，可以将 z 一分为三子字符串 (uvw=z)，例如：
1)|uv|<=N;
2)|v|>=1;
3)For each k>=0, uv^kw in L.
N 必须小于或等于接受 L 的 DFA 的最小状态数。所以要应用抽水引理，我需要知道有多少状态将具有接受 L 的最小 DFA。有没有办法知道有多少状态将具有倒退？那么在不建立最小 DFA 的情况下是否可以知道最少的状态数？
N 必须小于或等于接受 L 的 DFA 的最小状态数
N 不能小于接受 L 的最小 DFA 中的状态数；否则，DFA 不能接受 L（如果可以，您将有一个接受 L 的 DFA 小于接受 L 的最小 DFA，这是矛盾的）。我们可以安全地假设 N 等于接受 L 的最小 DFA 中的状态数（这样的 DFA 是唯一的）。
因此，要应用抽水引理，我需要知道有多少个州将具有接受 L 的最小 DFA
严格来说，这不是真的。在大多数引理证明中，实际上 N 是多少并不重要。您只需确保目标字符串满足其他属性。给定一个 DFA，可以确定最小 DFA 将具有多少个状态；但是，如果您有 DFA，则无需担心泵引理，因为您已经知道 L 是正则的。事实上，确定一个 N 使得有 N 个状态接受 L 的最小 DFA 构成了所讨论语言确实是正则的有效证明。
那么是否有可能在不构建最小 DFA 的情况下知道最少的状态数？
通过分析语言的描述并使用 Myhill-Nerode 定理，可以构建一个语言是规则的证明并找到最小 DFA 中的状态数，而无需实际构建最小 DFA（尽管一旦你完成了这种使用 Myhill-Nerode 的证明，最小 DFA 的构造是一个简单的练习）。您还可以使用 Myhill-Nerode 作为抽水引理的替代方法来证明语言不规则，通过显示语言的最小 DFA 需要有无限多的状态，这是一个矛盾。
请让我知道这些观察结果是否回答了您的问题；我很乐意提供额外的说明。