11

所以这不是关于抽水引理及其工作原理，而是关于先决条件。

在网络上你可以读到的任何地方，常规语言都必须通过抽引引理，但是没有人谈论有限语言，它实际上是常规语言的一部分。

所以我们可能都同意，以下语言是一种有限语言，也是一种常规语言，但它绝对没有通过抽水引理：

L = {'abc', 'defghi'}

请告诉我是否根本没有人写它，或者我们为什么错了——甚至没有。

4

4 回答 4

16

有限语言使用抽水引理的原因是因为你可以使抽水长度比语言中最长的单词长。如维基百科（我没有我的计算理论书）所述，抽水引理如下：

令L为常规语言。那么存在一个整数p ≥ 1 仅取决于L使得L中长度至少为p的每个字符串w（p称为“泵送长度”）可以写成w = xyz（即w可以分为三个子串），满足以下条件：

  1. | 是| ≥1
  2. | xy | ≤ p
  3. 对于所有i ≥ 0，xy i z ∈ L

现在，考虑一些有限语言L，让k = max w ∈ L | w | 是L中最长单词的长度。然后我声称L的最小泵送长度是p = k +1。由于L中没有长度至少为k +1 的单词，因此（空洞地）每个这样的单词都满足三个条件（或者，实际上，您想指定的任何其他条件）是真的。

当然，您可以看到任何有限语言都是正则的（正则语言在有限联合下是封闭的，并且一个单词的所有语言都是正则的），但请注意，此论点并未表明这一点；重要的是要记住，虽然可以抽取任何常规语言，但存在可以抽取但不规则的语言。

于 2012-08-06T17:14:12.257 回答
5

“在为常规语言抽取引理的背景下”

是的，我们同意，所有有限语言都是正则语言意味着我们可以拥有有限自动机以及任何有限语言的正则表达式。
而a infinite language may be regular or not. 维恩图如下所示。所以我们只需要检查无限的语言 L，它的规则不是！

想想FA：

  • 任何automatafor 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 +操作！

[答案]有限语言的自动机中没有循环，所以我们不能泵送（通过重复生成）语言中的新字符串。并且 Pumping Lemma 不适用于有限语言。

尽管一些作者还解释了有限语言的抽引引理，其中ixy i z 可以有界地重复（比如 k ≤ i ≤ m ）

在此处输入图像描述

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

于 2012-11-24T09:08:52.627 回答
0

有一种最简单的方法可以证明某种语言是无限的。假设 L 是某个正则表达式 E，L(E) 的语言。

假设 L(E) 等价于{ab^nc | n ≥ 0}。

我们知道 E 的形式是ab*c，并且我们知道这种语言可能是正则的（我们不能证明某些东西是正则的），因为这个结论的泵引理是k = 0，换句话说，xz = ac，并且每个正则表达式都有一个等价的自动机.

结论很简单，如果 DFA 有一些状态可以转换到自己，那么语言是无限的。

     a   b   c

 q0  q1    
 q1     q1  q2
*q2

q1 具有到自身的过渡，因此 L(E) 是无限的。

于 2015-04-21T15:39:33.027 回答
-1

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

无法通过抽水引理并不意味着语言不规则。实际上，要使用抽水引理，您的语言必须在其定义中具有某种闭包。如果您的语言只是一组单词，则没有什么可以“泵入”其中的。

于 2012-08-06T17:03:42.153 回答