math - 确保: Pumping lemma for infinite regular languages only?

Question

因此，这与抽水引理及其工作原理无关，而与先决条件有关。

在网络上的任何地方，您都可以阅读到常规语言必须通过激进的引理，但是现在任何人都在谈论有限语言，而有限语言实际上是常规语言的一部分。

因此，我们可能都同意，以下语言既是有限语言，又是常规语言，但绝对不会通过激进的引理:
L = {'abc', 'defghi'}
请告诉我，如果根本没有人写过这句话，或者告诉我为什么我们错了-甚至没有。

Answer 1

有限语言可以处理泵送引理的原因是，您可以使泵送长度比语言中最长的单词更长。泵激引理as stated on Wikipedia(我没有我的计算理论书):

Let L be a regular language. Then there exists an integer p ≥ 1 depending only on L such that every string w in L of length at least p (p is called the "pumping length") can be written as w = xyz (i.e., w can be divided into three substrings), satisfying the following conditions:

1. |y| ≥ 1
2. |xy| ≤ p
3. for all i ≥ 0, xyⁱz ∈ L

现在，考虑某种有限语言L，令k = maxw∈L | w |。是L中最长字的长度。然后我声称L的最小抽运长度为p = k + 1。由于L中没有长度至少为k + 1的单词，因此每个单词都满足这三个条件(或者实际上是您要指定的任何其他条件)是(很虚假的)事实。

您可以看到，任何有限的语言都是规则的(当然，规则语言在有限的并集下是封闭的，并且一个单词的所有语言都是规则的)，但是请注意，此参数并未显示此内容。重要的是要记住，尽管可以泵送任何常规语言，但 there exist languages that can be pumped but are not regular。