Rog*_*llo 6 computability finite-automata regular-language formal-languages kleene-star
我在一本关于可计算性的书中读过这篇文章:
(Kleene定理)当且仅当它可以通过应用三个运算联合,连接,重复有限次数从有限语言获得时,语言是规则的.
我正在与"有限语言"斗争.
考虑这种语言: L = a*
它不是有限的.它是一个{0, a, aa, aaa, ...}显然是无限集(0=空字符串)的集合.
所以这是一种无限的语言,对吗？也就是说,"无限集"意味着"无限语言",对吧？
显然,这a*是一种常规语言.它是一种无限的语言.因此,通过Kleene的定理,它不能成为常规语言.矛盾.
我糊涂了.我想我不知道"有限语言"是什么意思.
你走在正确的轨道上，它可能会更清楚。克莱恩定理表达了三个陈述的等价性
语言是正则的 == 语言可以用正则表达式表示 == 语言可以用有限自动机表示。
你的例子确实是一种常规语言。有限语言就是您所期望的那样，一种可以在有限时间内列出的语言。
当他们谈论重复时，他们谈论的是 Kleen Star 操作，这正是a*代表的集合{empty, a, aa, aaa, aaaa, ...}
编辑：
我找到了这个链接：克莱恩斯定理，它很有帮助。他们所说的“重复”指的是克林星，那么原来的说法就有意义了。a*是Kleen_Star(a)