确保:仅对无限的常规语言提供引理? [英] To make sure: Pumping lemma for infinite regular languages only?

问题描述

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

So this is not about the pumping lemma and how it works, it's about a pre-condition.

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

Everywhere in the net you can read, that regular languages must pass the pumping lemma, but noweher anybody talks about finite languages, which actually are a part of regular languages.

所以我们可能都同意，以下语言既是有限语言，又是常规语言，但绝对不会通过激进式引理:

So we might all aggree, that the following language is a finite language as well as it's a regular one, but it definitely does not pass the pumping lemma:

L = {'abc', 'defghi'}

请告诉我是否只是没有人写过这本书，或者为什么我们错了-甚至没有.

Please, tell me if simply no one writes about it or why we're wrong - or even not.

推荐答案

有限语言用于抽水引理的原因是因为您可以使抽水长度比该语言中最长的单词更长.如Wikipedia所述， )如下:

The reason that finite languages work with the pumping lemma is because you can make the pumping length longer than the longest word in the language. The pumping lemma, as stated on Wikipedia (I don't have my theory of computation book with me) is the following:

让 L 为常规语言.然后存在一个仅取决于 L 的整数 p ≥1，因此长度 L 中的每个字符串 w 至少 p ( p 被称为泵送长度")可以写为 w = xyz (即， w 可以分为三个子字符串)，满足以下条件:

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. 对于所有 i ≥0， xy ⁱ z ∈ L

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

现在，考虑一些有限的语言 L ，让 k = max _{w ∈ L} | w |是 L 中最长单词的长度.然后，我声称​​ L 的最小抽运长度为 p = k +1.由于在 L 中没有没有单词，长度至少为 k +1，所以每是(虚假地)成立>这样的词满足三个条件(或者实际上是您要指定的任何其他条件).

Now, consider some finite language L, and let k = max_{w ∈ L} |w| be the length of the longest word in L. Then I claim that the minimal pumping length for L is p = k+1. Since there are no words in L with length at least k+1, it is (vacuously) true that every such word satisfies the three conditions (or, indeed, any other condition you care to specify).

您当然可以看到任何有限的语言都是规则的(规则语言在有限的并集下是封闭的，并且一个单词的所有语言都是规则的)，但是请注意，此参数并未显示此内容；重要的是要记住，尽管可以泵送任何常规语言，但存在可以泵送但不能被泵送的语言常规.

You can see that any finite language is regular, of course (regular languages are closed under finite union, and all languages of one word are regular), but note that this argument doesn't show this; it's important to remember that while any regular language can be pumped, there exist languages that can be pumped but are not regular.

这篇关于确保:仅对无限的常规语言提供引理?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！