regular-language - 无限的语言不可能是正则的吗？什么是有限语言？

Question

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

(Kleene's Theorem) A language is regular if and only if it can be obtained from finite languages by applying the three operations union, concatenation, repetition a finite number of times.

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

考虑这种语言:L = a*

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

所以它是一种无限的语言，对吧？也就是说，“无限集合”意味着“无限语言”，对吗？

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

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

Answer 1

你走在正确的轨道上，它可能会更清晰。克莱恩定理表达了三个陈述的等价

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

你的例子确实是一种常规语言。有限语言就是您所期望的那样，一种可以在有限时间内列出的语言。

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

编辑:

我找到了this link: Kleenes Theorem这很有帮助。他们所说的“重复”指的是克林星，那么原来的说法就有意义了。 a* 是 Kleen_Star(a)