11

我在一本关于可计算性的书中读到了这一点:

(Kleene's Theorem) 一种语言是规则的当且仅当它可以通过应用联合、连接、重复有限次数这三个操作从有限语言中获得。

我正在与“有限的语言”作斗争。

考虑这种语言:L = a*

它不是有限的。它{0, a, aa, aaa, ...}显然是一个无限集(0=空字符串)。

所以它是一种无限的语言,对吧?也就是说,“无限集”意味着“无限语言”,对吧?

显然,a*是一种常规语言。它是一种无限的语言。因此,根据 Kleene 定理,它不可能是常规语言。矛盾。

我很困惑。我想我不知道“有限语言”是什么意思。

4

5 回答 5

4

很快,您的声明就是说:

当且仅当存在正则表达式时,语言才是正则的。


“可以通过应用三个操作联合,连接,重复有限次数从有限语言中获得”部分本质上是正则表达式的快速口头定义。通常,正则表达式 (RE) 从以下基本情况开始正式定义:

  • ∅(空集)是一个 RE
  • ε(空字符串)是一个 RE
  • a是 RE,其中a在字母表中

这些都是有限的语言。然后,我们通过有限次应用以下三个递归规则来获得其他 RE :

  • 一个| B是 RE,其中AB都是 RE
  • AB是 RE,其中AB都是 RE
  • A*是 RE,其中A是 RE

最后,您可以使用有限描述(正则表达式)创建无限语言。

于 2014-07-07T14:59:44.583 回答
4

您走在正确的轨道上,可能会更清楚。Kleen 定理表达了三个陈述的等价性

一种语言是正则的 == 一种语言可以用正则表达式表示 == 一种语言可以用有限自动机表示。

您的示例确实是一种常规语言。一种有限的语言是你所期望的,一种可以在有限的时间内列出的语言。

当他们在谈论重复时,他们在谈论 Kleen Star 操作,这正是a*代表,集合{empty, a, aa, aaa, aaaa, ...}

编辑:

我找到了这个链接:Kleenes Theorem这很有帮助。他们所说的“重复”是指 Kleen Star,那么原来的陈述是有道理的。a*Kleen_Star(a)

于 2013-07-01T20:05:45.630 回答
3

有限语言是包含有限数量单词的语言。最简单的情况是根本不包含单词、空字符串和由单个符号组成的单个字符串(例如a在您的示例中)。

我认为您的困惑来自误读您引用的规则(正如一些评论问题的人一样)。

(Kleene's Theorem) 一种语言是规则的当且仅当它可以通过应用联合、连接、重复有限次数这三个操作从有限语言中获得。

这篇文章不是在谈论在一种语言中创建所有字符串所需的字符串操作数量,而是关于定义所定义语言所需的更简单语言的操作数量。您提到的语言是通过从有限语言(集合 {“a”})开始并应用重复运算符一次来构建的。

一种不同的、不太直接的表达方式将不诉诸语言和对语言的操作,而是诉诸于表示语言的表达式和组合它们的更复杂的表达式:当且仅当它可以由包含有限数量的运算符。

取一个类似的表达式a,表示仅包含单个单词“a”的有限语言。我们可以向该表达式添加一个重复运算符,我们得到a*,包含来自第一种语言的零个或多个单词的每个连接的无限语言。我们可以通过从表示有限语言的表达式开始并使用模式E = F |组合一个或两个较小的表达式FG来构建每个有限表达式E GE = FGE = F* 将表示常规语言。表示有限语言(词数有限的语言)的表达式是用表达式陈述规则时的基本情况;当规则直接用语言表述时,有限语言是基本情况,没有任何绕道表达域。

如果我们允许无限多次应用并集、连接和重复(或者等效地,如果我们允许使用正则表达式规则的无限表达式),则不能保证生成的语言是正则的。这与观察到无限大的上下文无关文法可以定义非上下文无关语言的常规语言级别类似,如 van Wijngaarden 文法所示。

于 2015-03-12T02:00:57.560 回答
-1

具有有限数量的字符串的语言是有限语言。

因为字符串是有限的,所以可以使用它们来创建有限自动机。Kleene 定理是 (1) 任何正则语言都可以被有限自动机接受。反之亦然:(2)有限自动机接受的任何语言都是规则的。请注意,自动机可能是确定性的,也可能不是确定性的。

现在,当一种语言是无限的(它有无限数量的字符串)时,它可能是乔姆斯基层次结构中的任何类型的语言(常规或非常规)。

于 2021-10-19T16:07:35.757 回答
-2

无限语言意味着具有无限等价类的集合。然而,a* 语言只有一个等价类,因此它是一种有限语言。

于 2016-05-07T04:55:04.240 回答