regular-language - 从书中抽引理证明是错误的吗?

Question

《计算理论导论》一书中“pumping lemma”的证明：

抽水引理：如果 A 是正则语言，则有一个数 p（抽水长度），其中如果 s 是 A 中长度至少为 p 的任何字符串，则 s 可分为三段，s = xyz，满足以下条件：

1. 对于每个 i ≥ 0，xyiz ∈ A，
2. |是| > 0，并且
3. |xy| ≤ p

令 M = (Q, Σ, δ, q1, F) 是识别 A 的 DFA。我们将泵送长度 p 指定为 M 的状态数。我们证明 A 中长度至少为 p 的任何字符串 s 可能被分成三块xyz，满足我们的三个条件。如果 A 中没有长度至少为 p 的字符串怎么办？那么我们的任务就更容易了，因为这个定理变得空洞地正确：显然，如果没有任何这样的字符串，这三个条件对于所有长度至少为 p 的字符串都成立。

问题：粗体引用部分，我认为这是错误的。因为如果 A 中没有长度至少为 p 的字符串，那么它显然不是常规语言。

Answer 1

这里有两点需要澄清：

1. 抽水引理指出，“如果一种语言是规则的，那么该语言中所有长度至少为 p 的字符串都有一些属性。” 如果您的语言没有任何长度至少为 p 的字符串，则该陈述在没有反例的意义上是空洞的。如果 x 为假，“如果 x，则 y”在数学上为真。“如果月亮是奶酪做的，那么我就是法国国王”在数学上是正确的陈述。这可能与我们通常使用条件的方式略有不同，我们假设假设通常（有条件地，假设地）为真。但这是它的正式含义。
2. 任何字符串长度不小于 p 的语言都有长度严格小于 p 的字符串。因为字符串的长度必须是非负整数，这意味着长度是有限的。因为每个字符串长度对应于语言字母表上有限多个可能的字符串，并且有限多个有限项的总和必须是有限的，所以任何这样的语言都必​​须是有限的。我们知道，无论抽水引理说什么，有限语言都必须是正则的；无论如何，常规语言的引理并不关心这种情况，所以这里所说的是真的还是假的真的无关紧要。简单地对具有较短字符串的语言什么都不说，而不是试图指出它的声明对于这些情况也是一致的，这将不会令人困惑。