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

Question

我在一本书（Hromkovic, Communication Complexity and Parallel Computating）中读到有无数种仅由一个元素组成的非递归-可枚举（非 RE）语言？但那可能吗？我认为对于非 RE（甚至不可判定）的语言，语言必须是无限的。

Answer 1

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

1. 作者写了一些不同的东西，你的解释不正确；
2. 作者写了一些与他们意图不同的东西，可能使用了草率的术语；
3. 由于对不属于他们专业的主题的误解，作者写了一些不正确的东西。

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