是否存在仅由1个元素组成的非RE语言？

Question

我在一本书（Hromkovic，通信复杂性和并行计算）中读到，存在无限数量的非递归 - 可枚举（非RE）语言，它们只由1个元素组成？但这可能吗？我认为，对于非RE（或甚至不可判断）的语言，语言必须是无限的。

Answer 1

不，所有有限语言都是规则的，因为它们可以被有限自动机接受。您阅读的内容至少有三种可能的解释：

1. 作者写了一些不同的东西，你的意思是错误的;
2. 作者写了一些不同于他们想要的东西，可能使用了草率的术语;
3. 由于对不属于其专业的主题的误解，作者写了不正确的内容。

如果您引用相关段落，则有可能探索哪些选项最有可能。请注意，每个人都会犯错误 - 读书的人和写书的人都一样。另请注意，我使用的是作者而不是作者，因为这段文章可能是由一位作者单独编写的，并且没有经过适当的审核。