要确保:仅为无限常规语言提供引理？

Question

所以这不是关于泵浦引理及其工作原理,而是关于先决条件.

你可以阅读网络中的任何地方,常规语言必须通过抽取引理,但现在任何人都会谈论有限语言,它实际上是常规语言的一部分.

所以我们可能都是aggree,以下语言是有限语言,也是常规语言,但它肯定不会通过泵引理:

L = {'abc', 'defghi'}

请告诉我,如果没有人写它或为什么我们错了 - 甚至没有.

Answer 1

有限语言与泵浦引理一起工作的原因是因为你可以使泵送长度长于语言中最长的单词.维基百科上所说的抽水引理(我没有我的计算理论书)如下:

让L成为常规语言.然后存在一个整数p仅取决于≥1 大号使得每个字符串瓦特在大号长度至少的p(p被称为"泵送长度")可被写为瓦特 = XYZ(即,瓦特可分为三个子串),满足以下条件:

1. | y | ≥1
2. | xy | ≤ p
3. 对于所有我 ≥0,XY ^我 ž ∈ 大号

现在,考虑一些有限的语言大号,让ķ = MAX _{w ^ ∈ 大号} | w | 是L中最长单词的长度.然后我声称L的最小泵浦长度是p = k +1.因为有没有在口头上大号,长度至少ķ +1,它是(空洞地)真的,每一个这样的话满足三个条件(或者更确切地说,你关心任何其他条件指定).

当然,你可以看到任何有限的语言是常规的(常规语言在有限联合下是封闭的,并且一个单词的所有语言都是常规的),但请注意,这个参数没有显示出来; 重要的是要记住,虽然可以抽取任何常规语言,但是存在可以抽取但不常规的语言.

Answer 2

“在为常规语言泵送语法方面”

是的，我们同意，所有有限语言都是常规语言，这意味着我们可以具有有限自动机以及任何有限语言的正则表达式。
而a infinite language may be regular or not。Venn-Diagram如下所示。因此，我们只需要检查无规律的L语言就可以了！

考虑一下FA：

• 任何（automata用于操作）。a finite language can not contains loop!regular expressions for finite language will be without * and +

• 任何automata对a infinite language(regular) will contain the loop。We can't construct an automata for infinite language without loop; 其中循环可能是通过其他某种状态的自循环。{如果它的自循环，则单个符号重复任意数量的时间，如果通过其他状态，符号序列进入循环，则可以重复任意数量的时间}。

抽水意味着重复。在抽奖中，w可以将x，y，z分为三个部分。“ y”部分w发生在循环中（即y> = 1）。因此，抽奖引理无非是找到循环部分y并重复该循环部分任意次数的时间。
您可以查看是否重复循环任何次数并生成w'仍以语言显示的新字符串。

注意：Regular Expressions for infinite language can't be without * and +操作！

[answer]自动机中没有针对有限语言的循环，因此我们无法泵送（通过重复生成）语言中的新字符串。而且抽引引数不适用于有限语言。

尽管有些作者还解释了有限语言的泵送引理，其中ixy ⁱ z可以有界地重复（例如k？i？m）

在维恩图中，每个有限集都是规则的。无限集可以是规则的，也可以不是规则的。 Regular-Languages ? Non-Regular Languages

Answer 3

根据定义，有限语言是正则语言，因为您可以通过仅表达所有单词的并集来构建满足它的正则表达式（例如，(abc)|(defghi)满足您的语言的正则表达式），因此您可以拥有满足它的确定性有限自动机。

无法通过泵引理并不意味着该语言不规则。事实上，要使用泵引理，您的语言必须在其定义中具有某种闭包。如果您的语言只是一组单词，则其中没有任何内容可以“泵送”。