有限语言是包含有限数量单词的语言。最简单的情况是根本不包含单词、空字符串和由单个符号组成的单个字符串(例如a
在您的示例中)。
我认为您的困惑来自误读您引用的规则(正如一些评论问题的人一样)。
(Kleene's Theorem) 一种语言是规则的当且仅当它可以通过应用联合、连接、重复有限次数这三个操作从有限语言中获得。
这篇文章不是在谈论在一种语言中创建所有字符串所需的字符串操作数量,而是关于定义所定义语言所需的更简单语言的操作数量。您提到的语言是通过从有限语言(集合 {“a”})开始并应用重复运算符一次来构建的。
一种不同的、不太直接的表达方式将不诉诸语言和对语言的操作,而是诉诸于表示语言的表达式和组合它们的更复杂的表达式:当且仅当它可以由包含有限数量的运算符。
取一个类似的表达式a
,表示仅包含单个单词“a”的有限语言。我们可以向该表达式添加一个重复运算符,我们得到a*
,包含来自第一种语言的零个或多个单词的每个连接的无限语言。我们可以通过从表示有限语言的表达式开始并使用模式E = F |组合一个或两个较小的表达式F和G来构建每个有限表达式E G、E = FG或E = F* 将表示常规语言。表示有限语言(词数有限的语言)的表达式是用表达式陈述规则时的基本情况;当规则直接用语言表述时,有限语言是基本情况,没有任何绕道表达域。
如果我们允许无限多次应用并集、连接和重复(或者等效地,如果我们允许使用正则表达式规则的无限表达式),则不能保证生成的语言是正则的。这与观察到无限大的上下文无关文法可以定义非上下文无关语言的常规语言级别类似,如 van Wijngaarden 文法所示。